The familiar world twisted and blurred for Abd-Elmohaymen. After a long, arduous day serving his nation, he drifted into a deep sleep, only to awaken in the bewildering, whispered depths of the Unknown – a forest straight out of an old folktale. There, waiting for him, were his loyal friends, Sam07a, the quick-witted strategist, and Omar, the ever-pragmatic observer, seemingly pulled into this same vivid dreamscape.
Lost amidst talking animals, unsettling shadows, and whimsical, yet often dangerous, characters, their only hope lies in deciphering the forest's enigmatic challenges. Each problem in this set describes a unique predicament they face within this strange, beautiful, and sometimes unsettling dream. By solving them, you guide Sam07a, Omar, and Abd-Elmohaymen through the labyrinthine Unknown, and perhaps, help Abd-Elmohaymen find his way back to his waking world.
To begin this grand journey, as a sign of solidarity and encouragement for Abd-Elmohaymen, please print the following phrase: Go Abd Go!
Prepare to journey into the heart of the Unknown. Their adventure awaits!
Welcome to the Unknown...
Go Abd Go!
welcome to the Unknown
Go Abd Go!
Having navigated the treacherous Spirit-Oak Grove, the three found their path leading to a quaint, dilapidated mill. Inside, they found two eccentric figures: Adham, a gruff but jovial miller with flour perpetually dusting his beard, and his perpetually bewildered apprentice, Halzoom.
It seemed Adham and Halzoom had a long-standing tradition of challenging each other with cryptic number puzzles. This time, Adham, having just won their latest bout, decided to present Halzoom with a particularly fiendish one, but it immediately caught Sam07a's strategic eye.
"Listen closely, Halzoom!" Adham bellowed, tapping a chalk-dusted finger on a grimy chalkboard. "Given two incredibly large numbers, $$$L$$$ and $$$R$$$, you must count the number of ordered pairs of integers $$$(a,b)$$$ that satisfy these precise conditions:"
- $$$(L \le a \le b \le R)$$$
- $$$b \bmod a = b + a - 2 \cdot (a \,\&\, b)$$$ (where "&" denotes the bitwise AND operation)
Halzoom scratched his head, already looking overwhelmed. But Abd-Elmohaymen, recognizing a deep mathematical challenge, nudged Sam07a. "This sounds like something the Old Man of the Woods would set! If we solve it for them, perhaps they'll show us the way to the Whispering Bridge." Abd-Elmohaymen, meanwhile, was fascinated by the bitwise AND operation, wondering what strange magic it might represent.
The answer to such a puzzle could be astronomically large, so Adham added a final, critical instruction: "Since the answer can be very large, present it modulo $$$10^9 +7$$$ !"
Help Sam07a, Omar, and Abd-Elmohaymen solve Adham and Halzoom's perplexing problem to earn their passage through the mill.
Two integers $$$L$$$ , $$$R$$$ $$$(1\leq L \leq R \leq 10^{18})$$$
Print the number of ordered pairs of integers $$$(a , b)$$$ that meet both the condition modulo $$$10^9 + 7$$$.
5 9
8
After their success at Adham and Halzoom's mill, the friends found themselves at the foot of an enormous, ancient tree, unlike any they had seen. Its branches spiraled upwards into the misty canopy, forming a complex, sprawling network. Abd-Elmohaymen, ever the one to explore, recognized it as a legendary "Whispering Tree," said to hold the secrets of the forest in its very structure.
A shimmering inscription appeared on its gnarled trunk: "To find the truest path within, from root to leaf, a number win. Walk but one way, from top to floor, and values join, to ask for more. Build with digits, what you find, the largest number, of its kind."
It explained that the tree was rooted at node 0. Each node had a unique 'spirit value' (a single digit from 1 to 9). They were allowed to choose two nodes and take the shortest path between them. As they walked, they had to collect the spirit value of each node they visited, adding it to an empty sequence. Once they reached a leaf node, this sequence of collected digits would form a large number.
Sam07a immediately understood: they needed to find the path that, when its node values were concatenated, would form the largest possible number. Omar worried about the sheer number of paths, while Abd-Elmohaymen was determined to find the "truest" (and largest) number hidden within the tree's whispers. They knew they couldn't delete or reorder any digits – the path defined the number.
The example diagram showed a path from node 1 (green) to node 5 (red) forming the number 95928, which was the largest for that small tree. The tree in front of them, however, was massive, though its height (depth) didn't seem to exceed 150 levels.
Help Sam07a, Omar, and Abd-Elmohaymen find the largest number they can obtain by traversing a single path in the Whispering Tree.
Illustration of the first sample case. The first line will contain the number of nodes $$$n$$$ $$$(1 \le n \le 5*10^5)$$$.
The second line will contain $$$n$$$ values $$$a_i(1 \le a_i \le 9 , 0 \le i \le n-1 )$$$ where $$$a_i$$$ is the value of the $$$ith$$$ node.
The next $$$n-1$$$ lines contain two integers $$$u$$$ , $$$v$$$ $$$(0 \le u,v \le n-1)$$$ indicating an edge between $$$u$$$ and $$$v$$$.
Output the largest number you can obtain.
6 5 9 3 9 2 8 0 1 0 2 0 3 3 4 4 5
95928
Just when the three friends thought they were making progress through the Elderwood, a chilling presence descended. The air grew heavy, and the shadows seemed to twist into sinister forms. From the deepest part of the forest, the gravelly voice of the Beast echoed, its words seeping into their minds like cold mist.
"Welcome, little travelers," the Beast rumbled, its unseen form seemingly everywhere at once. "To truly test your cunning, you must play my game. Succeed, and your path may clear. Fail, and you shall wander these woods eternally."
A flat, obsidian stone appeared before them, acting as a "blackboard." On it, the Beast magically inscribed an even number $$$N$$$ copies of the number $$$1$$$.
"This is a game for two players," the Beast explained."One of you shall be Player A, the other Player B. In each round:
- Player A chooses two numbers, $$$a$$$ and $$$b$$$, from the stone and erases them.
- Player B then writes either their sum $$$(a + b)$$$ or their absolute difference $$$(|a - b|)$$$ back onto the stone.
- One of the numbers on the stone became larger than the sum of all other numbers currently on the stone.
- All numbers on the stone became zero.
"Now for the stakes," the Beast continued, a hint of cruel amusement in its voice."At the very end, Player B must give Player A a certain number of enchanted cookies. This number will be equal to the number of numbers remaining on the stone when the game ends."
"Player A," the Beast directed, its gaze seemingly fixed on Sam07a, "you wish to gain as many cookies as possible. Player B," it then turned its attention to Omar, "you wish to give as few as possible."
Sam07a and Omar looked at each other, a grim determination setting in. Abd-Elmohaymen, ever the supportive friend, quickly realized that this was a strategic game, and they needed to determine the outcome if both players played optimally. The cookies weren't just a prize; they were rumored to possess properties that could reveal hidden paths.
How many cookies will Player A (Sam07a) receive if both players play optimally in the Beast's shadowy game?
A single $$$even$$$ integer $$$N$$$ $$$(2 \le N \le 10^7)$$$ the number of copies of $$$1$$$s.
The number of cookies Player A (Sam07a) will receive if both players play optimally in the Beast's shadowy game .
2
1
In Player A's turn, Player A must choose the two numbers on the board: $$$a=1$$$, $$$b=1$$$. Both are erased and the board is empty now. No matter what Player B chooses (2 from (1+1)) or (0 from (1-1)) , the game terminates, and there is always exactly one number left on the board. Therefore, Player A receives 1 cookie.
The Beast Adhoom, in its never-ending quest to confound, had left behind a large, mysterious grid plastered across a decaying wall in the Unknown. This grid was filled with strange, whispering letters, a silent message from the dark entity.
The three knew that deciphering these messages was crucial for their escape. They also found a smaller, equally cryptic string of characters. It seemed Adhoom had a unique way of hiding clues: a square area within the large grid would hold the next piece of their puzzle, but only if it contained each specific letter from the smaller string at least a certain number of times. The required count for each letter c was exactly F(c), which was the number of times $$$c$$$ appeared in the smaller string.
Their task was to find the smallest possible square area in the grid that met these conditions. If no such square existed anywhere in the vast grid, then Adhoom's riddle would remain unsolved, and they would be truly lost.
Help the three find the minimum possible area of such a square.
The first line of the input contains $$$n$$$ , $$$m$$$ , $$$k$$$ $$$(1 \leq n , m \leq 1000 , 1 \leq k \leq n \cdot{m})$$$.
The next $$$n$$$ lines consist of a string of length $$$m$$$ , describing the grid of lowercase letters.
The next line contains string $$$s$$$ of length $$$k$$$.
All strings consist of lowercase letters.
Print a single integer. The minimum possible area of a square that contains each letter $$$c$$$ at least $$$F(c)$$$ times, where $$$F(c)$$$ is the frequency of $$$c$$$ in $$$s$$$.
If such square doesn't exist , print -1.
5 5 5zzzzzdazzzhdzzzamssszzzzzadham
9
3 3 5sameahhhlsameh
9
After narrowly escaping the Beast's game, the three friends found themselves in a vast, ancient grove dominated by colossal, glowing Spirit-Oaks. These trees, according to Abd-Elmohaymen's ever-present "Unusual Flora of the Unknown" guide, resonate with different frequencies of spirit energy, measured by unique 'Resonance Values'. The forest was divided into $$$N$$$ distinct segments, and each segment $$$i$$$ had a Spirit-Oak with a specific resonance value $$$A_i$$$.
Their immediate goal was to find a 'Resonance Core' – a mystical artifact that required a precise combination of spirit energies to activate. The guide indicated that the Core would only appear if they could accurately determine the total 'strength' of a particular range of spirit energies within a specific section of the forest.
Periodically, a query would appear on a shimmering leaf: "How many Spirit-Oaks within segments $$$L$$$ to $$$R$$$ (inclusive) possess a Resonance Value between $$$X$$$ and $$$Y$$$ (inclusive)?"
Omar quickly realized this wasn't just about counting individual trees, but about summing up the presence of all trees whose resonance fell within a specific range. They knew the forest segments stretched for miles, and there would be many such queries. Only an efficient method would allow them to progress.
Can you help them calculate, for each query, the total count of Spirit-Oaks whose Resonance Values fall within the specified range $$$[X,Y]$$$ in the given forest segment $$$[L,R]$$$ ?
The first line contains two integers $$$N (1 \le N \le 10^5)$$$, the number of forest segments, and $$$Q (1 \le Q \le 10^5 )$$$, the number of queries.
The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \le A_i \le 10^5$$$), representing the Resonance Value of the Spirit-Oak in each segment.
The next $$$Q$$$ lines each contain four integers $$$L,R,X,Y (1 \le L \le R \le N, 1 \le X \le Y \le 10^5 )$$$, representing the start and end of the forest segment, and the lower and upper bounds for the Resonance Values.
For each query, print a single integer on a new line, representing the total count of Spirit-Oaks meeting the criteria.
7 51 2 1 3 2 7 22 5 1 21 4 1 11 6 2 37 7 2 21 7 8 10
3 2 3 1 0
The three found themselves in a peculiar grove. The trees here grew in perfectly geometric formations, and the leaves themselves held strange, mathematical properties. Omar, ever the observant one, noticed that a particular pattern of glowing moss on the ground formed a perfect isosceles triangle.
Sam07a, recalling tales of the Unknown's hidden truths, explained that within this grove, every significant geometric shape had two special points: its "Heart" (the center of its inscribed circle, or incenter) and its "Soul" (the center of its circumscribed circle, or circumcenter). The distance between these two points, he claimed, held the key to unlocking the grove's path.
This particular isosceles triangle, formed by the moss, had a base of length $$$B$$$ and two equal legs of length $$$L$$$. sam07a needed to determine the distance d between its Heart and its Soul.
"The Unknown reveals its paths not by light, but by understanding," Sam07a murmured, sketching in the dirt. "If we know the lengths of this triangle's base and legs, can we find the distance between its Heart and Soul?"
The single line of input contains two integers, $$$L$$$ and $$$B$$$ $$$(1 \le B , L \le 10^6)$$$, representing the length of the leg and the base of the isosceles triangle, respectively.
if no such triangle exists print $$$-1$$$ otherwise print the distance d between the circumcenter and incenter of the triangle. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
8 5
1.579084068
5 14
-1
Incenter: The center of the inscribed circle (the largest circle that fits inside the triangle, touching all three sides).
Circumcenter: The center of the circumscribed circle (the circle that passes through all three vertices of the triangle).
Sam07a, Omar, and Abd-Elmohaymen had only just stepped into the depths of the Unknown when they realized a crucial oversight. Their trusty "Unending Lantern" – a magical artifact that glowed perpetually – wasn't actually unending! It required a specific type of glowing moss, found only on ancient, gnarled trees, to keep its light strong.
Omar, ever practical, realized they needed to count how much moss they had collected. Each piece of moss, when placed in the lantern, burns for a certain number of hours. They have collected $$$N$$$ pieces of moss. For each piece $$$i$$$, they know it will burn for $$$H_i$$$ hours.
To ensure their path through the darkening forest remains illuminated, they need to know the total number of hours their lantern can stay lit if they use all the moss they have collected. They'll use one piece after another until all are gone.
Help Sam07a, Omar, and Abd-Elmohaymen calculate the total burn time.
An integer $$$N(1 \le N \le 1000)$$$ the number of pieces of moss. Then a line with $$$N$$$ integers $$$H_i(1 \le H_i \le 10^9)$$$. The number of hours the $$$i$$$th piece of moss will take to completely burn.
Print a single integer, the total burn time .
3 1 2 3
6
Just as they thought they had unraveled the Whispering Tree's secret, the three stumbled into a bewildering section of the Unknown. Paths here were not just paths; they were shimmering, ethereal lines connecting various mystical intersections. Local lore, quickly recalled by Abd-Elmohaymen, stated this was "Auntie Whispers' Labyrinth," a place designed to keep lost souls within its bounds.
Their goal was to travel from their current location, Intersection $$$1$$$, to the rumored exit, Intersection $$$N$$$. Each street (path) connecting two intersections had a peculiar property: a given percentage chance of passing through it safely, without alerting the labyrinth's unseen guardians. To escape, they needed to find a path from Intersection $$$1$$$ to Intersection $$$N$$$ that offered the highest possible chance of reaching their destination without being caught.
Suddenly, a spectral whisper echoed through the labyrinth, and Adham, who had mysteriously rejoined their company after his earlier game with Halzoom, felt a strange surge of energy. "I $$$\cdots$$$ I can do something!" he exclaimed. "I can make one street in this labyrinth completely safe! A guaranteed passage!" This was their one boon: a single street they could render $$$100\ \%$$$ safe, meaning a guaranteed passage with no risk.
Sam07a, remembering the old tales of Auntie Whispers, realized this was their one opportunity. Omar quickly began mapping the intersections and their probabilistic connections. They needed to find the optimal path, deciding where to use Adham's unique power to maximize their chances of escape.
Help Sam07a, Omar, Abd-Elmohaymen, and Adham find the path that gives them the highest chance of escaping Auntie Whispers' Labyrinth safely.
The first line contains two integers $$$n$$$ , $$$m$$$ ($$$1 \le n \le 10^5, n - 1 \le m \le \min(2 \cdot{10^5} , \ \frac{n\cdot(n - 1)}{2})$$$) the number of intersections and streets.
Then $$$m$$$ lines follow. The $$$i_{th}$$$ line contains $$$3$$$ integers $$$u_i$$$ , $$$v_i$$$ $$$(1 \leq u_i , v_i \leq n)$$$ and $$$p_i$$$ $$$(1 \leq p_i \leq 100)$$$ indicating a street between $$$u_i$$$ and $$$v_i$$$ with $$$p_i$$$ percentage chance of passing through it safely.
Print the probability as a percentage with exactly $$$6$$$ digits after the decimal point. The percentage value is considered correct if it differs by at most $$$10^{-6}$$$ from the judge output.
5 71 4 852 3 702 5 1003 5 801 2 503 4 903 1 70
100.000000
After securing enough Moonlit Moss to keep their lantern flickering, Sam07a, Omar, and Abd-Elmohaymen ventured deeper into a particularly ancient and silent part of the Unknown — the Elderwood. The trees were impossibly tall, their bark etched with glowing glyphs that shifted when no one looked directly at them.
Their journey came to a halt at a moss-covered stone monolith. As they approached, the surface shimmered and revealed a magical window into another part of the forest — a humble cabin hidden among the trees. Inside lived a curious engineer named Halzoom, famed not only for his inventions but also for brewing the finest magical coffee in the Unknown.
In that cabin, Halzoom faced a peculiar problem. His comical cat, 3ntar, had recently fallen in love with a mysterious, graceful feline who roamed the Elderwood. 3ntar, now struck by divine inspiration, demanded a coffee that matched his "love mood" — a special number $$$k$$$.
To prepare this enchanting blend, Halzoom turned to his experimental grid of coffee beans. Each cell in the grid held a smell strength, and the aroma of the final cup must come from a rectangle (submatrix) of beans whose total smell equals exactly $$$k$$$.
The beautiful cat that 3ntar fell in her love. His challenge? Find all rectangles (submatrices) in the grid where the sum of values is exactly $$$k$$$. For every value inside any of those rectangles, keep it. All other values must be changed to $$$0$$$.
Now, it's your task to help Halzoom, 3ntar, and the Elderwood explorers all at once — by solving this aromatic mystery.
The first line contains integers $$$n$$$, $$$m$$$, $$$k$$$ $$$(1 \le n, m \le 100,\ 0 \le k \le 10^4)$$$ — the number of rows, columns, and the desired total smell value.
The next $$$n$$$ lines contain $$$m$$$ integers each — the smell values in the grid $$$(0 \le a_{ij} \le 100)$$$.
Print the grid after finding all valid rectangles. Keep the values that are part of at least one rectangle with total sum $$$k$$$, and change all others to $$$0$$$.
5 5 51 1 1 1 51 7 1 1 11 1 1 1 11 1 1 1 11 1 1 1 5
1 0 1 1 5 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 5
In the first example:
The highlight on columns and rows, those submatrices will be printed with the same values.
The dense, whispering woods of the Unknown stretched endlessly before the three. After a particularly perplexing encounter with a musical grumpkin, they found themselves utterly lost. "If only Adham were here," sighed Omar, staring at a tangle of gnarled roots that looked suspiciously like a forgotten road. "He always knows the shortest path."
Just then, a peculiar figure emerged from the shadows – Adham, perched precariously on the back of a majestic, shimmering goose named Halzoom! Halzoom, it turns out, wasn't just any goose; she possessed an innate, almost magical, understanding of the forest's pathways.
Adham, ever the strategist, explained their predicament. The forest, he revealed, was a vast network of $$$N$$$ quaint, peculiar towns, connected by $$$M$$$ winding roads. Each road $$$i$$$ connected two towns, $$$u_i$$$ and $$$v_i$$$, and took a specific number of days, $$$w_i$$$, to traverse. Halzoom's magic wasn't about changing the speed of roads, but about finding the optimal set of paths.
However, there was a catch. Halzoom's magic only worked if they could choose exactly $$$N-1$$$ roads from the existing $$$M$$$ roads to form a specific type of travel network. This chosen set of $$$N-1$$$ roads, which Adham calls a "Halzoom Highway", must satisfy two crucial conditions:
- The chosen roads must form a tree on the $$$N$$$ towns. This means all towns must be connected, and there should be no cycles.
- For every pair of towns $$$u,v$$$, the shortest-travel-time between them on the "Halzoom Highway" (using the original $$$w_i$$$ days for the selected roads) must be exactly equal to the shortest-travel-time between them in the original forest (using all $$$M$$$ roads and their original $$$w_i$$$ days).
Adham, with a glint in his eye, turned to his friends. "Can you help me figure this out? We need to know if it's even possible to construct such a 'Halzoom Highway'!"
The first line contains two integers $$$N$$$ , $$$M$$$ ($$$1 \le N \le 2 \cdot{10^5}, N - 1 \le M \le \min(2 \cdot{10^5} , \ \frac{n\cdot(n - 1)}{2})$$$).
Then $$$M$$$ lines follow. The $$$i_{th}$$$ line contains 3 integers $$$u_i$$$ , $$$v_i$$$ $$$(1 \leq u_i , v_i \leq n)$$$ and $$$w_i$$$ $$$(1 \leq w_i \leq 10^9)$$$.
Print "YES" if there exists a tree that meets the above conditions , otherwise print "NO".
4 41 2 13 4 111 3 42 4 3
YES
4 41 2 13 4 21 3 42 4 3
NO
Sam07a, Omar, Abd-Elmohaymen had navigated countless perils in the Unknown. Now, at the very edge of the forest, blocking their path to freedom, stood Gamal. He wasn't just a chronicler; he was the enigmatic guardian of the Unknown's final secrets, and he would only allow them to pass if they could solve his ultimate riddle.
Gamal presented them with an array of $$$N$$$ peculiar leaves, each with an "essence value," $$$a_1,a_2, \cdots ,a_N$$$. To leave the Unknown, they had to count "Good Pairs" of these leaves.
A pair of leaves $$$(a_i,a_j)$$$ is a "Good Pair" if:
- $$$1 \le i \lt j \le N$$$,
- $$$\mathrm{lcm}(a_i, a_j)$$$ is a good number.
A number $$$x$$$ is considered good if, for every prime $$$p$$$ that divides $$$x$$$, $$$p^2$$$ also divides $$$x$$$.
Gamal's eyes gleamed. "Solve this, and the path is yours. Fail, and you shall forever remain a part of the Unknown!"
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of testcases.
For each testcase :
- Single integer $$$N$$$ $$$(2 \leq N \leq 10^5)$$$ — the size of the array.
- $$$N$$$ integers $$$a_1,a_2, \dots , a_n$$$ $$$(1 \leq a_i \leq 10^6)$$$
It is guaranteed that the sum of $$$N$$$ overall testcases does not exceed $$$2 \times 10^{5}$$$.
Print a single integer — the number of pairs $$$(i, j)$$$ satisfying the conditions above.
1510 18 29 36 20
1
The three, and Adham (with Halzoom) were deep in the Unknown. They met Abbas, an old man who cares for Halzoom. Abbas was worried. Halzoom, a special goose, had a strange eating plan, and it was hard to keep track.
Halzoom also had $$$M$$$ "3NTAR" cats (numbered $$$1$$$ to $$$M$$$) that needed food from his supply.
Here's Halzoom's feeding rule:
From Day 1: Each cat eats $$$1$$$ gram of dry food.
From Day 2: The food for cat $$$j$$$ on day $$$i$$$ is : (food for cat $$$j$$$ on day $$$i-1$$$) + (total food that cats $$$1$$$ to $$$j-1$$$ ate on the current day $$$i$$$).
Abbas needs help! He's particularly worried about the final meal: how much food will cat number $$$M$$$ eat on day $$$N$$$?
He needs this specific value to make sure Halzoom's provisions are managed correctly. If not, Halzoom might get upset, and its magic could go wrong.
The only one line contains two integers $$$N$$$ , $$$M$$$ ($$$1 \leq N, M \leq 10^6$$$), the number of days and number of cats.
Print the answer with mod $$$998244353$$$.
3 3
8
4 5
104
After all of that, Halzoom wants to say to you:
As the friends traversed a particularly whimsical clearing filled with chattering squirrels, they encountered a rather anxious-looking critter. "Oh dear, oh dear!" it squeaked, clutching a tiny abacus. "I've scattered my special enchanted nuts all across this clearing! Each nut holds a unique magical energy, represented by a number. I need to find two nuts whose combined energy is... odd! And if I find such a pair, I want the largest possible odd sum!"
Sam07a, intrigued by the squirrel's dilemma, recognized it as a peculiar challenge. Omar, always observant, started noting down the energy values of the nuts they saw scattered on the ground. Abd-Elmohaymen, convinced the squirrel was secretly a forest spirit, felt compelled to help.
The squirrel explained that it had already gathered N nuts, and it knew the energy value $$$A_i$$$ of each one. Their task was to help the squirrel determine if there existed any pair of different nuts whose energy values, when added together, resulted in an odd sum. If such a pair existed, they needed to find the maximum possible odd sum that could be formed. If no such pair could be found, the squirrel would be heartbroken, and they'd have to tell it $$$-1$$$.
Help them sort through the squirrel's scattered nuts and find the largest possible odd sum.
The first line contains a single integer $$$N$$$ $$$(2\leq N \leq 2 \cdot{10 ^ 5} )$$$ — the number of enchanted nuts.
The following line contains $$$n$$$ integers $$$A_i(1 \leq A_i \leq 2 \cdot{10 ^ 5})$$$ representing the energy value of each nut.
Print a single integer — the maximum possible odd sum of two elements, or $$$-1$$$ if no such pair exists.
63 5 6 1 8 10
15
Deep within the Halzoom's labyrinth, the three discovered an ancient, magical scroll, its text constantly shifting and rearranging itself. This was the Echoing Scroll of Fate, said to reveal the future, but only if its patterns were understood.
The scroll contained a long, secret message, a string of mystical characters. At various times, a whisper from the Unknown would activate a specific part of the scroll, a substring from index $$$L$$$ to $$$R$$$. For each such activation, a strange task appeared:
Find the Shortest Echo Cycle: They had to determine the minimum period of the characters in that specific part of the scroll $$$(S[L \cdots R])$$$. A period of a string is a prefix that can be used to generate the whole string by repeating the prefix. For example, the string "abcabcabc" has a length of $$$9$$$, but its minimum period is $$$3$$$ (because "abc" repeats). The minimum period of "ababab" is $$$2$$$.
Check the Scroll's Memory: They then had to recall if this exact minimum period had ever appeared as a minimum period from any previous query on this scroll.
Whisper of Reversal:
- If this minimum period was new (had not appeared in any past queries), the magic of the scroll would reverse the characters in that specific part of the scroll $$$(S[L \cdots R])$$$.
- If the minimum period had appeared before, the scroll would remain unchanged.
Abd-Elmohaymen, feeling the magical energy of the scroll, sensed that mastering its shifts was crucial for charting their destiny in this dream.
Your task is to help them manage the Echoing Scroll of Fate. After all queries, you must tell them what the new scroll is.
The first line contains two integers $$$N(1 \le N \le 10^5)$$$, the length of the scroll , $$$Q$$$ ($$$1 \le Q \le 10^5 $$$), the number of activations (queries), and a string $$$S$$$ of length $$$N$$$ consisting of lowercase English letters, representing the initial contents of the scroll.
The next $$$Q$$$ lines each contain two integers $$$L,R$$$ ($$$1 \le L \le R \le N$$$), representing the start and end of the substring for the current query.
You must print the new scroll after all queries.
9 3abcabcabc1 93 72 4
cacbbcaba
9 3jxngmvzku3 56 81 4
gmxjnkzvu