meetforever/GRPO_CL huggingface dataset:
user: You are given two binary strings $x$ and $y$, which are binary representations of some two integers (let's denote these integers as $f(x)$ and $f(y)$). You can choose any integer $k \ge 0$, calculate the expression $s_k = f(x) + f(y) \cdot 2^k$ and write the binary representation of $s_k$ in reverse order (let's denote it as $rev_k$). For example, let $x = 1010$ and $y = 11$; you've chosen $k = 1$ and, since $2^1 = 10_2$, so $s_k = 1010_2 + 11_2 \cdot 10_2 = 10000_2$ and $rev_k = 00001$.

For given $x$ and $y$, you need to choose such $k$ that $rev_k$ is lexicographically minimal (read notes if you don't know what does "lexicographically" means).

It's guaranteed that, with given constraints, $k$ exists and is finite.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 100$) — the number of queries.

Next $2T$ lines contain a description of queries: two lines per query. The first line contains one binary string $x$, consisting of no more than $10^5$ characters. Each character is either 0 or 1.

The second line contains one binary string $y$, consisting of no more than $10^5$ characters. Each character is either 0 or 1.

It's guaranteed, that $1 \le f(y) \le f(x)$ (where $f(x)$ is the integer represented by $x$, and $f(y)$ is the integer represented by $y$), both representations don't have any leading zeroes, the total length of $x$ over all queries doesn't exceed $10^5$, and the total length of $y$ over all queries doesn't exceed $10^5$.


-----Output-----

Print $T$ integers (one per query). For each query print such $k$ that $rev_k$ is lexicographically minimal.


-----Example-----
Input
4
1010
11
10001
110
1
1
1010101010101
11110000

Output
1
3
0
0



-----Note-----

The first query was described in the legend.

In the second query, it's optimal to choose $k = 3$. The $2^3 = 1000_2$ so $s_3 = 10001_2 + 110_2 \cdot 1000_2 = 10001 + 110000 = 1000001$ and $rev_3 = 1000001$. For example, if $k = 0$, then $s_0 = 10111$ and $rev_0 = 11101$, but $rev_3 = 1000001$ is lexicographically smaller than $rev_0 = 11101$.

In the third query $s_0 = 10$ and $rev_0 = 01$. For example, $s_2 = 101$ and $rev_2 = 101$. And $01$ is lexicographically smaller than $101$.

The quote from Wikipedia: "To determine which of two strings of characters comes when arranging in lexicographical order, their first letters are compared. If they differ, then the string whose first letter comes earlier in the alphabet comes before the other string. If the first letters are the same, then the second letters are compared, and so on. If a position is reached where one string has no more letters to compare while the other does, then the first (shorter) string is deemed to come first in alphabetical order."
user: You are given $n$ words, each of which consists of lowercase alphabet letters. Each word contains at least one vowel. You are going to choose some of the given words and make as many beautiful lyrics as possible.

Each lyric consists of two lines. Each line consists of two words separated by whitespace. 

A lyric is beautiful if and only if it satisfies all conditions below.   The number of vowels in the first word of the first line is the same as the number of vowels in the first word of the second line.  The number of vowels in the second word of the first line is the same as the number of vowels in the second word of the second line.  The last vowel of the first line is the same as the last vowel of the second line. Note that there may be consonants after the vowel. 

Also, letters "a", "e", "o", "i", and "u" are vowels. Note that "y" is never vowel.

For example of a beautiful lyric,  "hello hellooowww" 

"whatsup yowowowow"  is a beautiful lyric because there are two vowels each in "hello" and "whatsup", four vowels each in "hellooowww" and "yowowowow" (keep in mind that "y" is not a vowel), and the last vowel of each line is "o".

For example of a not beautiful lyric,  "hey man"

"iam mcdic"  is not a beautiful lyric because "hey" and "iam" don't have same number of vowels and the last vowels of two lines are different ("a" in the first and "i" in the second).

How many beautiful lyrics can you write from given words? Note that you cannot use a word more times than it is given to you. For example, if a word is given three times, you can use it at most three times.


-----Input-----

The first line contains single integer $n$ ($1 \le n \le 10^{5}$) — the number of words.

The $i$-th of the next $n$ lines contains string $s_{i}$ consisting lowercase alphabet letters — the $i$-th word. It is guaranteed that the sum of the total word length is equal or less than $10^{6}$. Each word contains at least one vowel.


-----Output-----

In the first line, print $m$ — the number of maximum possible beautiful lyrics.

In next $2m$ lines, print $m$ beautiful lyrics (two lines per lyric).

If there are multiple answers, print any.


-----Examples-----
Input
14
wow
this
is
the
first
mcdics
codeforces
round
hooray
i
am
proud
about
that

Output
3
about proud
hooray round
wow first
this is
i that
mcdics am

Input
7
arsijo
suggested
the
idea
for
this
problem

Output
0

Input
4
same
same
same
differ

Output
1
same differ
same same



-----Note-----

In the first example, those beautiful lyrics are one of the possible answers. Let's look at the first lyric on the sample output of the first example. "about proud hooray round" forms a beautiful lyric because "about" and "hooray" have same number of vowels, "proud" and "round" have same number of vowels, and both lines have same last vowel. On the other hand, you cannot form any beautiful lyric with the word "codeforces".

In the second example, you cannot form any beautiful lyric from given words.

In the third example, you can use the word "same" up to three times.
user: You are given an array $a$ of length $n$ and array $b$ of length $m$ both consisting of only integers $0$ and $1$. Consider a matrix $c$ of size $n \times m$ formed by following rule: $c_{i, j} = a_i \cdot b_j$ (i.e. $a_i$ multiplied by $b_j$). It's easy to see that $c$ consists of only zeroes and ones too.

How many subrectangles of size (area) $k$ consisting only of ones are there in $c$?

A subrectangle is an intersection of a consecutive (subsequent) segment of rows and a consecutive (subsequent) segment of columns. I.e. consider four integers $x_1, x_2, y_1, y_2$ ($1 \le x_1 \le x_2 \le n$, $1 \le y_1 \le y_2 \le m$) a subrectangle $c[x_1 \dots x_2][y_1 \dots y_2]$ is an intersection of the rows $x_1, x_1+1, x_1+2, \dots, x_2$ and the columns $y_1, y_1+1, y_1+2, \dots, y_2$.

The size (area) of a subrectangle is the total number of cells in it.


-----Input-----

The first line contains three integers $n$, $m$ and $k$ ($1 \leq n, m \leq 40\,000, 1 \leq k \leq n \cdot m$), length of array $a$, length of array $b$ and required size of subrectangles.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 1$), elements of $a$.

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($0 \leq b_i \leq 1$), elements of $b$.


-----Output-----

Output single integer — the number of subrectangles of $c$ with size (area) $k$ consisting only of ones.


-----Examples-----
Input
3 3 2
1 0 1
1 1 1

Output
4

Input
3 5 4
1 1 1
1 1 1 1 1

Output
14



-----Note-----

In first example matrix $c$ is:

 $\left(\begin{array}{l l l}{1} & {1} & {1} \\{0} & {0} & {0} \\{1} & {1} & {1} \end{array} \right)$ 

There are $4$ subrectangles of size $2$ consisting of only ones in it:

 [Image] 

In second example matrix $c$ is:

 $\left(\begin{array}{l l l l l}{1} & {1} & {1} & {1} & {1} \\{1} & {1} & {1} & {1} & {1} \\{1} & {1} & {1} & {1} & {1} \end{array} \right)$
user: You're given an array $b$ of length $n$. Let's define another array $a$, also of length $n$, for which $a_i = 2^{b_i}$ ($1 \leq i \leq n$). 

Valerii says that every two non-intersecting subarrays of $a$ have different sums of elements. You want to determine if he is wrong. More formally, you need to determine if there exist four integers $l_1,r_1,l_2,r_2$ that satisfy the following conditions:   $1 \leq l_1 \leq r_1 \lt l_2 \leq r_2 \leq n$;  $a_{l_1}+a_{l_1+1}+\ldots+a_{r_1-1}+a_{r_1} = a_{l_2}+a_{l_2+1}+\ldots+a_{r_2-1}+a_{r_2}$. 

If such four integers exist, you will prove Valerii wrong. Do they exist?

An array $c$ is a subarray of an array $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of every test case contains a single integer $n$ ($2 \le n \le 1000$).

The second line of every test case contains $n$ integers $b_1,b_2,\ldots,b_n$ ($0 \le b_i \le 10^9$). 


-----Output-----

For every test case, if there exist two non-intersecting subarrays in $a$ that have the same sum, output YES on a separate line. Otherwise, output NO on a separate line. 

Also, note that each letter can be in any case. 


-----Example-----
Input
2
6
4 3 0 1 2 0
2
2 5

Output
YES
NO



-----Note-----

In the first case, $a = [16,8,1,2,4,1]$. Choosing $l_1 = 1$, $r_1 = 1$, $l_2 = 2$ and $r_2 = 6$ works because $16 = (8+1+2+4+1)$.

In the second case, you can verify that there is no way to select to such subarrays.
user: You are creating a level for a video game. The level consists of $n$ rooms placed in a circle. The rooms are numbered $1$ through $n$. Each room contains exactly one exit: completing the $j$-th room allows you to go the $(j+1)$-th room (and completing the $n$-th room allows you to go the $1$-st room).

You are given the description of the multiset of $n$ chests: the $i$-th chest has treasure value $c_i$.

Each chest can be of one of two types:   regular chest — when a player enters a room with this chest, he grabs the treasure and proceeds to the next room;  mimic chest — when a player enters a room with this chest, the chest eats him alive, and he loses. 

The player starts in a random room with each room having an equal probability of being chosen. The players earnings is equal to the total value of treasure chests he'd collected before he lost.

You are allowed to choose the order the chests go into the rooms. For each $k$ from $1$ to $n$ place the chests into the rooms in such a way that:

  each room contains exactly one chest;  exactly $k$ chests are mimics;  the expected value of players earnings is minimum possible. 

Please note that for each $k$ the placement is chosen independently.

It can be shown that it is in the form of $\frac{P}{Q}$ where $P$ and $Q$ are non-negative integers and $Q \ne 0$. Report the values of $P \cdot Q^{-1} \pmod {998244353}$.


-----Input-----

The first contains a single integer $n$ ($2 \le n \le 3 \cdot 10^5$) — the number of rooms and the number of chests.

The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$) — the treasure values of each chest.


-----Output-----

Print $n$ integers — the $k$ -th value should be equal to the minimum possible expected value of players earnings if the chests are placed into the rooms in some order and exactly $k$ of the chests are mimics.

It can be shown that it is in the form of $\frac{P}{Q}$ where $P$ and $Q$ are non-negative integers and $Q \ne 0$. Report the values of $P \cdot Q^{-1} \pmod {998244353}$.


-----Examples-----
Input
2
1 2

Output
499122177 0 

Input
8
10 4 3 6 5 10 7 5

Output
499122193 249561095 249561092 873463811 499122178 124780545 623902721 0 



-----Note-----

In the first example the exact values of minimum expected values are: $\frac 1 2$, $\frac 0 2$.

In the second example the exact values of minimum expected values are: $\frac{132} 8$, $\frac{54} 8$, $\frac{30} 8$, $\frac{17} 8$, $\frac{12} 8$, $\frac 7 8$, $\frac 3 8$, $\frac 0 8$.
user: Warawreh created a great company called Nanosoft. The only thing that Warawreh still has to do is to place a large picture containing its logo on top of the company's building.

The logo of Nanosoft can be described as four squares of the same size merged together into one large square. The top left square is colored with red, the top right square is colored with green, the bottom left square is colored with yellow and the bottom right square is colored with blue.

An Example of some correct logos:

[Image]

An Example of some incorrect logos:

[Image]

Warawreh went to Adhami's store in order to buy the needed picture. Although Adhami's store is very large he has only one picture that can be described as a grid of $n$ rows and $m$ columns. The color of every cell in the picture will be green (the symbol 'G'), red (the symbol 'R'), yellow (the symbol 'Y') or blue (the symbol 'B').

Adhami gave Warawreh $q$ options, in every option he gave him a sub-rectangle from that picture and told him that he can cut that sub-rectangle for him. To choose the best option, Warawreh needs to know for every option the maximum area of sub-square inside the given sub-rectangle that can be a Nanosoft logo. If there are no such sub-squares, the answer is $0$.

Warawreh couldn't find the best option himself so he asked you for help, can you help him?


-----Input-----

The first line of input contains three integers $n$, $m$ and $q$ $(1 \leq n , m \leq 500, 1 \leq q \leq 3 \cdot 10^{5})$  — the number of row, the number columns and the number of options.

For the next $n$ lines, every line will contain $m$ characters. In the $i$-th line the $j$-th character will contain the color of the cell at the $i$-th row and $j$-th column of the Adhami's picture. The color of every cell will be one of these: {'G','Y','R','B'}.

For the next $q$ lines, the input will contain four integers $r_1$, $c_1$, $r_2$ and $c_2$ $(1 \leq r_1 \leq r_2 \leq n, 1 \leq c_1 \leq c_2 \leq m)$. In that option, Adhami gave to Warawreh a sub-rectangle of the picture with the upper-left corner in the cell $(r_1, c_1)$ and with the bottom-right corner in the cell $(r_2, c_2)$.


-----Output-----

For every option print the maximum area of sub-square inside the given sub-rectangle, which can be a NanoSoft Logo. If there are no such sub-squares, print $0$.


-----Examples-----
Input
5 5 5
RRGGB
RRGGY
YYBBG
YYBBR
RBBRG
1 1 5 5
2 2 5 5
2 2 3 3
1 1 3 5
4 4 5 5

Output
16
4
4
4
0

Input
6 10 5
RRRGGGRRGG
RRRGGGRRGG
RRRGGGYYBB
YYYBBBYYBB
YYYBBBRGRG
YYYBBBYBYB
1 1 6 10
1 3 3 10
2 2 6 6
1 7 6 10
2 1 5 10

Output
36
4
16
16
16

Input
8 8 8
RRRRGGGG
RRRRGGGG
RRRRGGGG
RRRRGGGG
YYYYBBBB
YYYYBBBB
YYYYBBBB
YYYYBBBB
1 1 8 8
5 2 5 7
3 1 8 6
2 3 5 8
1 2 6 8
2 1 5 5
2 1 7 7
6 5 7 5

Output
64
0
16
4
16
4
36
0



-----Note-----

Picture for the first test:

[Image]

The pictures from the left to the right corresponds to the options. The border of the sub-rectangle in the option is marked with black, the border of the sub-square with the maximal possible size, that can be cut is marked with gray.
user: You are given a range of positive integers from $l$ to $r$.

Find such a pair of integers $(x, y)$ that $l \le x, y \le r$, $x \ne y$ and $x$ divides $y$.

If there are multiple answers, print any of them.

You are also asked to answer $T$ independent queries.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 1000$) — the number of queries.

Each of the next $T$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le 998244353$) — inclusive borders of the range.

It is guaranteed that testset only includes queries, which have at least one suitable pair.


-----Output-----

Print $T$ lines, each line should contain the answer — two integers $x$ and $y$ such that $l \le x, y \le r$, $x \ne y$ and $x$ divides $y$. The answer in the $i$-th line should correspond to the $i$-th query from the input.

If there are multiple answers, print any of them.


-----Example-----
Input
3
1 10
3 14
1 10

Output
1 7
3 9
5 10
user: Kana was just an ordinary high school girl before a talent scout discovered her. Then, she became an idol. But different from the stereotype, she is also a gameholic. 

One day Kana gets interested in a new adventure game called Dragon Quest. In this game, her quest is to beat a dragon.[Image] 

The dragon has a hit point of $x$ initially. When its hit point goes to $0$ or under $0$, it will be defeated. In order to defeat the dragon, Kana can cast the two following types of spells.  Void Absorption 

Assume that the dragon's current hit point is $h$, after casting this spell its hit point will become $\left\lfloor \frac{h}{2} \right\rfloor + 10$. Here $\left\lfloor \frac{h}{2} \right\rfloor$ denotes $h$ divided by two, rounded down. Lightning Strike 

This spell will decrease the dragon's hit point by $10$. Assume that the dragon's current hit point is $h$, after casting this spell its hit point will be lowered to $h-10$.

Due to some reasons Kana can only cast no more than $n$ Void Absorptions and $m$ Lightning Strikes. She can cast the spells in any order and doesn't have to cast all the spells. Kana isn't good at math, so you are going to help her to find out whether it is possible to defeat the dragon.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 1000$)  — the number of test cases.

The next $t$ lines describe test cases. For each test case the only line contains three integers $x$, $n$, $m$ ($1\le x \le 10^5$, $0\le n,m\le30$)  — the dragon's intitial hit point, the maximum number of Void Absorptions and Lightning Strikes Kana can cast respectively.


-----Output-----

If it is possible to defeat the dragon, print "YES" (without quotes). Otherwise, print "NO" (without quotes).

You can print each letter in any case (upper or lower).


-----Example-----
Input
7
100 3 4
189 3 4
64 2 3
63 2 3
30 27 7
10 9 1
69117 21 2

Output
YES
NO
NO
YES
YES
YES
YES



-----Note-----

One possible casting sequence of the first test case is shown below: Void Absorption $\left\lfloor \frac{100}{2} \right\rfloor + 10=60$. Lightning Strike $60-10=50$. Void Absorption $\left\lfloor \frac{50}{2} \right\rfloor + 10=35$. Void Absorption $\left\lfloor \frac{35}{2} \right\rfloor + 10=27$. Lightning Strike $27-10=17$. Lightning Strike $17-10=7$. Lightning Strike $7-10=-3$.
user: Two villages are separated by a river that flows from the north to the south. The villagers want to build a bridge across the river to make it easier to move across the villages.

The river banks can be assumed to be vertical straight lines x = a and x = b (0 < a < b).

The west village lies in a steppe at point O = (0, 0). There are n pathways leading from the village to the river, they end at points A_{i} = (a, y_{i}). The villagers there are plain and simple, so their pathways are straight segments as well.

The east village has reserved and cunning people. Their village is in the forest on the east bank of the river, but its exact position is not clear. There are m twisted paths leading from this village to the river and ending at points B_{i} = (b, y'_{i}). The lengths of all these paths are known, the length of the path that leads from the eastern village to point B_{i}, equals l_{i}.

The villagers want to choose exactly one point on the left bank of river A_{i}, exactly one point on the right bank B_{j} and connect them by a straight-line bridge so as to make the total distance between the villages (the sum of |OA_{i}| + |A_{i}B_{j}| + l_{j}, where |XY| is the Euclidean distance between points X and Y) were minimum. The Euclidean distance between points (x_1, y_1) and (x_2, y_2) equals $\sqrt{(x_{1} - x_{2})^{2} +(y_{1} - y_{2})^{2}}$.

Help them and find the required pair of points.


-----Input-----

The first line contains integers n, m, a, b (1 ≤ n, m ≤ 10^5, 0 < a < b < 10^6). 

The second line contains n integers in the ascending order: the i-th integer determines the coordinate of point A_{i} and equals y_{i} (|y_{i}| ≤ 10^6). 

The third line contains m integers in the ascending order: the i-th integer determines the coordinate of point B_{i} and equals y'_{i} (|y'_{i}| ≤ 10^6). 

The fourth line contains m more integers: the i-th of them determines the length of the path that connects the eastern village and point B_{i}, and equals l_{i} (1 ≤ l_{i} ≤ 10^6).

It is guaranteed, that there is such a point C with abscissa at least b, that |B_{i}C| ≤ l_{i} for all i (1 ≤ i ≤ m). It is guaranteed that no two points A_{i} coincide. It is guaranteed that no two points B_{i} coincide.


-----Output-----

Print two integers — the numbers of points on the left (west) and right (east) banks, respectively, between which you need to build a bridge. You can assume that the points on the west bank are numbered from 1 to n, in the order in which they are given in the input. Similarly, the points on the east bank are numbered from 1 to m in the order in which they are given in the input.

If there are multiple solutions, print any of them. The solution will be accepted if the final length of the path will differ from the answer of the jury by no more than 10^{ - 6} in absolute or relative value.


-----Examples-----
Input
3 2 3 5
-2 -1 4
-1 2
7 3

Output
2 2
user: Methodius received an email from his friend Polycarp. However, Polycarp's keyboard is broken, so pressing a key on it once may cause the corresponding symbol to appear more than once (if you press a key on a regular keyboard, it prints exactly one symbol).

For example, as a result of typing the word "hello", the following words could be printed: "hello", "hhhhello", "hheeeellllooo", but the following could not be printed: "hell", "helo", "hhllllooo".

Note, that when you press a key, the corresponding symbol must appear (possibly, more than once). The keyboard is broken in a random manner, it means that pressing the same key you can get the different number of letters in the result.

For each word in the letter, Methodius has guessed what word Polycarp actually wanted to write, but he is not sure about it, so he asks you to help him.

You are given a list of pairs of words. For each pair, determine if the second word could be printed by typing the first one on Polycarp's keyboard.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 10^5$) — the number of pairs to check. Further input contains $n$ descriptions of pairs.

The first line of each description contains a single non-empty word $s$ consisting of lowercase Latin letters. The second line of the description contains a single non-empty word $t$ consisting of lowercase Latin letters. The lengths of both strings are not greater than $10^6$.

It is guaranteed that the total length of all words $s$ in the input is not greater than $10^6$. Also, it is guaranteed that the total length of all words $t$ in the input is not greater than $10^6$.


-----Output-----

Output $n$ lines. In the $i$-th line for the $i$-th pair of words $s$ and $t$ print YES if the word $t$ could be printed by typing the word $s$. Otherwise, print NO.


-----Examples-----
Input
4
hello
hello
hello
helloo
hello
hlllloo
hello
helo

Output
YES
YES
NO
NO

Input
5
aa
bb
codeforces
codeforce
polycarp
poolycarpp
aaaa
aaaab
abcdefghijklmnopqrstuvwxyz
zabcdefghijklmnopqrstuvwxyz

Output
NO
NO
YES
NO
NO