Svetozar lives in an ordinary apartment building on floor $$$n$$$. As in any similar building around here, the entrance and the exit are on the first floor.
One day he needed to go outside, and he decided not to take the elevator, but to go down the stairs. A sudden question "how many steps are there between two floors?" led curious Svetozar to start counting the steps between floors. When he finished counting, he realized that he had accidentally gone up and ended up one floor higher! But now he knows that there are exactly $$$x$$$ steps between every two adjacent floors.
Now he needs to go down the stairs from floor $$$(n + 1)$$$ to the first floor. How many steps will Svetozar have to take?
The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 100$$$): the floor Svetozar lives on.
The second line contains an integer $$$x$$$ ($$$2 \leq x \leq 100$$$): the number of steps between two adjacent floors.
It is guaranteed that floor $$$n$$$ is not the last floor of the building.
Print an integer: the number of steps from floor $$$n + 1$$$ to the first floor.
420
80
67
42
In the first sample, Svetozar went up from the fourth floor to the fifth, and now he needs to go down one floor $$$4$$$ times. Therefore, he will have to walk $$$80$$$ steps.
Svetozar does not go outside without a reason, of course. He has very important business in another district of the city. But how can he get there? Luckily, the city where Svetozar lives has a metro – and not an ordinary one, but one with a circular line!
The circular line consists of $$$n$$$ stations, numbered consecutively from $$$1$$$ to $$$n$$$ clockwise. Between any two neighboring stations there is a bidirectional segment: between stations $$$1$$$ and $$$2$$$, between $$$2$$$ and $$$3$$$, $$$\ldots$$$, between $$$n - 1$$$ and $$$n$$$, and also between $$$n$$$ and $$$1$$$. Trains can travel in both directions.
The fare for traveling along one segment between stations $$$u$$$ and $$$v$$$ depends on their numbers:
Svetozar is at station $$$s$$$ and needs to get to station $$$f$$$ ($$$s \ne f$$$). Find the minimum cost of such a trip in coins, using only the circular metro line.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$): the number of test cases. Then, $$$t$$$ test cases follow.
The only line of a test case contains integers $$$n$$$, $$$s$$$, and $$$f$$$ ($$$3 \leq n \leq 10^9$$$, $$$1 \leq s, f \leq n$$$, $$$s \ne f$$$): the number of stations on the line and the starting and ending stations of the trip.
For each test case, print the minimum cost of the trip from station $$$s$$$ to station $$$f$$$ on a separate line.
85 1 56 1 65 1 46 1 43 1 23 3 16 2 367 60 7
213312115
In the first two test cases of the sample, it is cheapest to travel one station counterclockwise. Thus, the cost of the trip is $$$2$$$ coins in the first test case (because the station numbers have the same parity) and $$$1$$$ coin in the second test case (because the parities are different).
In the third test case, Svetozar should travel two stations counterclockwise for $$$2 + 1 = 3$$$ coins.
Svetozar got off the metro in a neighborhood of the city completely unlike his own. Colorful signs with lots of letters, placed everywhere, were a delight to the eye.
The walk was long. Out of boredom, Svetozar started looking at the signs and searching them for palindromic substrings of length $$$3$$$. You should also say whether such a palindrome appears on the sign.
Recall that a substring is a contiguous fragment of a string. A string is a palindrome if it reads the same left to right and right to left, and its length is the number of characters in it. For example, the strings aba and aaa are palindromes of length $$$3$$$, the string abb is not a palindrome, and the string abba is a palindrome, but not of length $$$3$$$.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$): the number of test cases. Then, $$$t$$$ test cases follow.
The only line of a test case contains a string $$$s$$$ ($$$1 \leq |s| \leq 2 \cdot 10^5$$$) of lowercase English letters: the contents of the sign.
It is guaranteed that the sum of the lengths of the strings $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print YES if the string $$$s$$$ contains a palindromic substring of length $$$3$$$, and NO otherwise. You may print the words in any case.
7abaabcaaaabbaaaaabcbdd
YESNONONONOYESYES
In the fifth test case of the sample, the string abba itself is a palindrome, but its substrings of length $$$3$$$ – abb and bba – are not palindromes.
Svetozar's favorite number is the number $$$n$$$. His favorite color is red. His favorite geometric shape is a square. And his least favorite activity is logo design.
That is why he assigned this to you. The requirements for the logo are simple:
Generate any logo that satisfies the conditions above.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$): the number of test cases. Then, $$$t$$$ test cases follow.
The only line of a test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$): the number of red squares in the logo.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, print the logo in the following format.
In the first line, print an integer $$$m$$$ ($$$1 \leq m \leq 10^6$$$).
In the next $$$m$$$ lines, print the logo: each line must contain exactly $$$m$$$ characters '#' (a red square) or '.' (an uncolored square).
If there are several valid logos, print any.
31210
1#2##..4#######.###.....
Svetozar is also a programmer, but he writes code in magical programming languages.
Today his program contains an array $$$a$$$ of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Svetozar wants to sort it in non-decreasing order, that is, make each next element not less than the previous one.
The magic of the programming language is not yet under Svetozar's control, so he can only perform operations of the following kind: swap two adjacent elements $$$a_i$$$ and $$$a_{i+1}$$$, but only if their sum is odd. This operation may be applied any number of times (including zero). If Svetozar tries to swap other pairs of numbers, he will not succeed.
Determine whether Svetozar can make the array non-decreasing, or whether his abilities are not enough for that.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$): the number of test cases. Then, $$$t$$$ test cases follow.
The first line of a test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$): the length of the array.
The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$): the elements of the array.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print YES if the array can be made non-decreasing, and NO otherwise, on a separate line. You may print the words in any case.
441 6 3 233 1 214252 4 6 8 10
NONOYESYES
34-3 2 -1 41-10000000004-5 -7 0 2
YESYESNO
Consider the second sample. In the first test case, it is enough to swap the two adjacent numbers $$$2$$$ and $$$-1$$$ to make the array non-decreasing. In the second test case, the array is already non-decreasing, so nothing needs to be swapped. In the third test case, it can be shown that it is impossible to make the array non-decreasing by swapping adjacent numbers while following the rules.
Svetozar often chats with his friends in messaging apps. He dislikes typos, so he decided to clean them out of messages that look like laughter.
Laughter is a non-empty string of odd length in which one fixed vowel and one fixed consonant alternate. In other words, laughter has one of two forms:
Here $$$v$$$ is some vowel and $$$c$$$ is some consonant; both letters are the same throughout the laughter. In particular, any single letter is laughter. The vowels are the letters 'a', 'e', 'i', 'o', and 'u'. All other lowercase English letters are considered consonants (including the letter 'y').
Help Svetozar implement this: for a given string $$$s$$$ of lowercase English letters, find its longest subsequence that is laughter. If there are several such subsequences, print the lexicographically smallest one.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$): the number of test cases. Then, $$$t$$$ test cases follow.
The only line of a test case contains a string $$$s$$$ ($$$1 \leq |s| \leq 2 \cdot 10^5$$$) of lowercase English letters.
It is guaranteed that the sum of the lengths of the strings $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print the required subsequence on a separate line. If there are several suitable subsequences of maximum length, print the lexicographically smallest of them.
7ahahahhahhaajajhazaababayayoklolkek
ahahahahahaaaabayaykkek
In the first test case of the sample, the subsequence ahahahahaha is suitable. In the third test case of the sample, the string ab has even length and is not laughter, so the answer is the letter 'a'. In the fifth test case of the sample, the letter 'y' is a consonant, and the whole string yay is laughter.
Recall that a subsequence is obtained from a string by deleting zero or more characters without changing the order of the remaining ones. A sequence $$$x$$$ is lexicographically smaller than a sequence $$$y$$$ if one of the following two conditions holds:
You have $$$2n$$$ cards, and a positive integer $$$a_i$$$ is written on the $$$i$$$-th of them. Determine whether there exists a positive integer $$$x$$$ such that the cards can be split into two groups of $$$n$$$ cards each with the following properties:
If so, find any such number.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$): the number of test cases. Then, $$$t$$$ test cases follow.
The first line of a test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).
The second line contains $$$2n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{2n}$$$ ($$$1 \leq a_i \leq 10^9$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print an integer: a suitable value of $$$x$$$. If there are several suitable values, print any of them. If no suitable value of $$$x$$$ exists, print $$$-1$$$.
512 812 328 2 4 121 6 2 3267 67 67 67
4-12-167
In the first test case of the sample, for example, $$$x = 2$$$, $$$x = 4$$$, and $$$x = 8$$$ work.
In the second test case, there is no suitable value of $$$x$$$.
This is an interactive problem.
Svetozar wants to play a game with you. He has thought of a lowercase English letter. You may ask him questions in order to guess it.
In one question, you may give Svetozar a string $$$s$$$ of even length $$$2k$$$ consisting of lowercase English letters. In response, he will delete exactly half of the characters from the string at his discretion and tell you the resulting string. The only requirement he follows is: if the chosen letter occurs in the string $$$s$$$, he must delete at least one of its occurrences.
Use your intelligence to guess the letter! You may ask at most $$$26$$$ questions, but if Svetozar realizes that you have asked clearly more questions than needed to guess the letter, you lose.
To ask the next question, print on a separate line a string $$$s$$$ of lowercase English letters of even length ($$$2 \leq |s| \leq 700$$$). Then read a string of length $$$|s| / 2$$$ denoting Svetozar's reply.
You may ask at most $$$26$$$ questions, but if you ask a clearly suboptimal number of questions, the reply will be a string consisting of $$$|s| / 2$$$ characters '-' (hyphen). In that case, the program must terminate immediately, and the solution will receive the verdict "Wrong answer". If the program does not do this in that situation, the verdict may be undefined.
When the letter is found, print the string ! c, where $$$c$$$ is the found letter, and terminate the program correctly. After printing the answer, you should not read anything.
After each output, including the answer, print a newline and flush the output stream so that the program runs correctly and receives the correct verdict. To do this, you can use fflush(stdout) or std::cout.flush() in C++, System.out.flush() in Java, and sys.stdout.flush() in Python.
ab
aabb ! a
In the sample, after one question, the program decided to report that the chosen letter is 'a', although from that single answer it is impossible to uniquely determine which of the $$$26$$$ letters was chosen.
Blank lines are shown for clarity only. There are no blank lines in the actual interaction.
Svetozar started a channel on a popular video platform. His very first video was a huge success! On day $$$i$$$ it received $$$a_i$$$ likes, where $$$a_i$$$ is a nonnegative integer.
Unfortunately, after yet another redesign that buried the like counter behind six or seven menus, one has to press a great many buttons to obtain the full statistics, or even contact support!
Still, Svetozar does not need the full statistics yet. He has kept $$$n$$$ measurements showing that at the end of day $$$d_j$$$ the total number of likes was $$$s_j$$$ (for $$$j = 1, 2, \ldots, n$$$). Thus, $$$a_1 + a_2 + \ldots + a_{d_j} = s_j$$$.
Svetozar is interested in how many likes there could have been over $$$T$$$ consecutive days, considering only the first $$$d_n$$$ days. In other words, find the maximum theoretically possible sum $$$a_\ell + a_{\ell+1} + \ldots + a_{\ell+T-1}$$$ subject to $$$1 \leq \ell \leq d_n - T + 1$$$. Of course, a period of $$$T$$$ days need not start or end exactly on the days $$$d_1, d_2, \ldots, d_n$$$ for which the measurements are already available.
The first line contains integers $$$n$$$ and $$$T$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq T \leq 10^6$$$): the number of measurements and the length of the period.
The next $$$n$$$ lines contain integers $$$d_j$$$ and $$$s_j$$$: the measurement day and the total number of likes by the end of that day. It is guaranteed that $$$d_n \geq T$$$, that $$$1 \leq d_1 \lt d_2 \lt \ldots \lt d_n \leq 10^6$$$, and that $$$1 \leq s_1 \leq s_2 \leq \ldots \leq s_n \leq 10^9$$$.
Print an integer: the maximum possible number of likes over $$$T$$$ consecutive days.
3 22 44 96 12
9
In the sample, one possible sequence is $$$(0, 4, 5, 0, 3, 0)$$$. It is consistent with all measurements. On the second and third days, $$$4 + 5 = 9$$$ likes were received. No two consecutive days can yield more likes.
A dark magic shop has received the newest numeric tape made of antimatter. The tape is infinite in one direction and consists of cells with non-negative integers written on them: the number $$$0$$$ is written at the finite end, then the numbers $$$1$$$, $$$2$$$, $$$3$$$, $$$\ldots$$$, and so on to infinity.
For his research, Svetozar urgently needs a contiguous segment $$$[L, R]$$$ of this tape, and not just any segment, but one such that the bitwise XOR of all its numbers equals a given magic number $$$A$$$.
Magical goods are not cheap, so he needs a suitable segment with the smallest possible $$$R$$$. You may find any valid value of $$$L$$$. Anyway, when buying, the tape still has to be cut up to $$$R$$$ inclusive.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$): the number of test cases. Then, $$$t$$$ test cases follow.
The only line of a test case contains an integer $$$A$$$ ($$$0 \leq A \leq 10^{18}$$$).
For each test case, print integers $$$L$$$ and $$$R$$$ ($$$0 \leq L \leq R \leq 10^{18}$$$) on a separate line: the bounds of a suitable segment. $$$R$$$ must be as small as possible. If there are several valid values of $$$L$$$ for the smallest $$$R$$$, print any.
It can be shown that under the given constraints at least one solution exists.
801234567
0 01 12 21 21 42 46 63 4
Recall that the bitwise XOR of two non-negative integers $$$x$$$ and $$$y$$$ is a non-negative integer $$$z$$$ whose binary representation has a bit equal to $$$1$$$ if the corresponding bits of $$$x$$$ and $$$y$$$ differ, and $$$0$$$ if they coincide.
A new artistic composition has appeared in the local art gallery; all of its paintings were painted by Svetozar. The composition consists of $$$n \cdot m$$$ paintings arranged in a grid of $$$n$$$ rows and $$$m$$$ columns of paintings. The painting in row $$$i$$$ and column $$$j$$$ has height $$$h_{i,j}$$$ and width $$$w_{i,j}$$$ centimeters.
The evil mage Arglwyddytywyllwch is already making plans for these paintings. Every day he comes to the gallery and dreams of the composition ending up in his castle. The idea is as follows: he wants to crop some of the paintings (that is, decrease their height and/or width, keeping them rectangular) so that:
This is done so that all paintings can be glued into one large canvas with no gaps. The plan is silent on the artistic value of such a canvas.
It is allowed not to crop the paintings at all if the conditions are already satisfied. Rotating the paintings and swapping them is forbidden. At the same time, Arglwyddytywyllwch wants to minimize the total area of the scraps and is interested in how small the scraps can be in principle.
Every day Arglwyddytywyllwch comes to the gallery, and every day, at the whim of Svetozar's muse, one of the paintings is replaced with another, the newest one. Find the minimum total area of scraps after each painting replacement.
Note that the paintings are cropped only hypothetically, whereas the replacements are quite real and are applied sequentially one after another.
The first line contains integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n, m, k \leq 2 \cdot 10^5$$$, $$$n \cdot m \leq 2 \cdot 10^5$$$): the dimensions of the composition in paintings and the number of days.
The next $$$n$$$ lines contain $$$2m$$$ integers each. The $$$i$$$-th of them contains the integers $$$h_{i,1}$$$, $$$w_{i,1}$$$, $$$h_{i,2}$$$, $$$w_{i,2}$$$, $$$\ldots$$$, $$$h_{i,m}$$$, $$$w_{i,m}$$$.
Then, $$$k$$$ lines describing the painting replacements follow. Each replacement is given by integers $$$x$$$, $$$y$$$, $$$h$$$, $$$w$$$ ($$$1 \leq x \leq n$$$, $$$1 \leq y \leq m$$$) and replaces the painting $$$(x, y)$$$ with a new painting of size $$$h \times w$$$.
All sizes satisfy $$$1 \leq h, w \leq 10^6$$$.
For each painting replacement, print an integer: the minimum total area of scraps after this replacement.
2 3 44 5 3 8 3 106 4 5 7 5 101 2 7 62 1 2 101 1 1 12 3 8 20
41 92 127 237
Svetozar is the reigning world champion in the rock-paper-scissors game. Today the Candidates Tournament is taking place; its winner will challenge Svetozar for the next title.
Each match consists of a single round in which the players simultaneously choose one of the three options. As is well known, rock beats scissors, scissors beat paper, paper beats rock; if both players show the same action, the referee tosses a coin, and either player may become the winner with probability $$$\frac{1}{2}$$$.
The Candidates Tournament bracket is a binary tree of matches: the candidates stand at the leaves, and at each internal vertex the winners of its two subtrees play. Svetozar is not in the bracket, but his future match against the winner of the Candidates Tournament will follow the same rules.
For a fair and unbiased selection, the match tree is height-balanced, that is, for every vertex the heights of the subtrees differ by at most $$$1$$$.
Analysts from Svetozar's team have studied all games of the current season, and for each candidate the distribution with which he chooses rock, scissors, and paper is known. It may be assumed that a player follows his distribution in every match independently of who his opponent is.
Svetozar wants to know the probability that he wins if he now chooses rock, scissors, or paper as his action in the title match. Help him find these probabilities.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$): the number of test cases. Then, $$$t$$$ test cases follow.
The first line of a test case contains an integer $$$n$$$ ($$$1 \leq n \lt 2 \cdot 10^5$$$): the number of vertices of the tree.
The next line contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters 'n' and 'p'. It describes the vertices of the tournament tree in the order of their first visit in a preorder traversal. The tree is built from this string as follows. Create a tree with a single root vertex and scan the characters of the string from left to right.
Then there is one line for each letter 'p' in $$$s$$$ (from left to right). Each such line contains integers $$$a_i$$$, $$$b_i$$$, and $$$c_i$$$ ($$$0 \leq a_i, b_i, c_i \leq 100$$$, $$$a_i + b_i + c_i = 100$$$): the probabilities that the corresponding candidate chooses rock, scissors, and paper, in percent.
It is guaranteed that in the string $$$s$$$ the number of letters 'p' equals the number of letters 'n' plus one.
It is guaranteed that the constructed tree is height-balanced, that is, for every vertex the heights of its left and right subtrees differ by at most $$$1$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print three integers: the probabilities that Svetozar can defeat the winner of the Candidates Tournament if he chooses rock, scissors, and paper against him, respectively, modulo $$$998\,244\,353$$$.
Formally, let $$$M = 998\,244\,353$$$. It can be shown that each value in the answer can be represented as an irreducible fraction $$$P / Q$$$, where $$$P$$$ and $$$Q$$$ are integers and $$$Q \not \equiv 0 \pmod{M}$$$. Instead of printing $$$f = P / Q$$$, print an integer $$$r$$$ such that $$$0 \leq r \lt M$$$ and $$$r \cdot Q \equiv P \pmod{M}$$$.
41p100 0 03npp100 0 00 100 03npp50 50 050 50 05npnpp67 13 2020 26 5410 11 79
499122177 0 1499122177 0 1249561089 748683265 499122177126346277 983129554 387890700
Note that the input lists probabilities in the order rock, scissors, and paper, which is not the same as in the name RPS (rock, paper, and scissors).
The answers for the test cases in decoded form:
You are given $$$m$$$ answers to range sum queries on a binary (that is, consisting only of zeros and ones) array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$: each answer $$$(\ell, r, s)$$$ means that $$$a_\ell + a_{\ell + 1} + \ldots + a_r = s$$$.
Find any binary array that satisfies all the answers. The array is not necessarily unique; if several arrays exist, find any of them. The query answers may contradict each other, in which case you must report that no such array exists.
The first line contains integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 5000$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$): the number of elements in the array and the number of range sum query results.
The next $$$m$$$ lines contain integers $$$\ell$$$, $$$r$$$, and $$$s$$$ ($$$1 \leq \ell \leq r \leq n$$$, $$$0 \leq s \leq r - \ell + 1$$$): the sum on the segment $$$[\ell, r]$$$ must equal $$$s$$$.
If no suitable array exists, print NO.
Otherwise, print YES on the first line, and $$$n$$$ integers on the second line, each equal to $$$0$$$ or $$$1$$$: any array that satisfies all the queries.
You may print the words YES and NO in any case.
4 21 3 22 4 1
YES 1 0 1 0
5 31 4 12 5 35 5 1
NO
In the first sample, the array $$$(1, 1, 0, 0)$$$ is also valid.
In the second sample, it can be shown that the first two results contradict each other, which means that no such array exists.
After the Land of Gnomes was freed from evil, Svetozar was unanimously elected as the administrator, who now has to decide how best to organize the defense against evil mages.
At the next general assembly, all gnomes lined up in a row. The gnome numbered $$$i$$$ in the row has a hat of color $$$a_i$$$ on their head. Svetozar wants to choose several consecutive gnomes for the Council of the Land of Gnomes. But if strictly more than half of the gnomes in the Council wear hats of the same color, they will form an absolute majority. Svetozar does not yet know what consequences an absolute majority might have, but he fears it in advance.
For now, Svetozar is only considering which gnomes to choose. From time to time, he asks you one of two types of questions:
The first line contains integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$): the number of gnomes and the number of Svetozar's questions.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$): the colors of the gnomes' hats.
Then, $$$q$$$ questions follow, one per line, in one of the two formats described above:
For each question of the second type, print an integer: the color of the absolute majority for the given set of gnomes, or $$$-1$$$ if there is no such color.
6 101 1 2 3 4 42 1 42 1 32 2 52 5 61 3 12 1 32 3 61 6 12 1 62 4 5
-1 1 -1 4 1 -1 1 -1
After the questions of the first type, the hat colors of the gnomes will look like $$$(1, 1, 1, 3, 4, 4)$$$ and $$$(1, 1, 1, 3, 4, 1)$$$ respectively.