meetforever/GRPO_CL huggingface dataset:
user: Overlooking the captivating blend of myriads of vernal hues, Arkady the painter lays out a long, long canvas.

Arkady has a sufficiently large amount of paint of three colours: cyan, magenta, and yellow. On the one-dimensional canvas split into n consecutive segments, each segment needs to be painted in one of the colours.

Arkady has already painted some (possibly none or all) segments and passes the paintbrush to you. You are to determine whether there are at least two ways of colouring all the unpainted segments so that no two adjacent segments are of the same colour. Two ways are considered different if and only if a segment is painted in different colours in them.


-----Input-----

The first line contains a single positive integer n (1 ≤ n ≤ 100) — the length of the canvas.

The second line contains a string s of n characters, the i-th of which is either 'C' (denoting a segment painted in cyan), 'M' (denoting one painted in magenta), 'Y' (one painted in yellow), or '?' (an unpainted one).


-----Output-----

If there are at least two different ways of painting, output "Yes"; otherwise output "No" (both without quotes).

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


-----Examples-----
Input
5
CY??Y

Output
Yes

Input
5
C?C?Y

Output
Yes

Input
5
?CYC?

Output
Yes

Input
5
C??MM

Output
No

Input
3
MMY

Output
No



-----Note-----

For the first example, there are exactly two different ways of colouring: CYCMY and CYMCY.

For the second example, there are also exactly two different ways of colouring: CMCMY and CYCMY.

For the third example, there are four ways of colouring: MCYCM, MCYCY, YCYCM, and YCYCY.

For the fourth example, no matter how the unpainted segments are coloured, the existing magenta segments will prevent the painting from satisfying the requirements. The similar is true for the fifth example.
user: Let $f_{x} = c^{2x-6} \cdot f_{x-1} \cdot f_{x-2} \cdot f_{x-3}$ for $x \ge 4$.

You have given integers $n$, $f_{1}$, $f_{2}$, $f_{3}$, and $c$. Find $f_{n} \bmod (10^{9}+7)$.


-----Input-----

The only line contains five integers $n$, $f_{1}$, $f_{2}$, $f_{3}$, and $c$ ($4 \le n \le 10^{18}$, $1 \le f_{1}$, $f_{2}$, $f_{3}$, $c \le 10^{9}$).


-----Output-----

Print $f_{n} \bmod (10^{9} + 7)$.


-----Examples-----
Input
5 1 2 5 3

Output
72900

Input
17 97 41 37 11

Output
317451037



-----Note-----

In the first example, $f_{4} = 90$, $f_{5} = 72900$.

In the second example, $f_{17} \approx 2.28 \times 10^{29587}$.
user: Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse. For example, strings "pop", "noon", "x", and "kkkkkk" are palindromes, while strings "moon", "tv", and "abab" are not. An empty string is also a palindrome.

Gildong loves this concept so much, so he wants to play with it. He has $n$ distinct strings of equal length $m$. He wants to discard some of the strings (possibly none or all) and reorder the remaining strings so that the concatenation becomes a palindrome. He also wants the palindrome to be as long as possible. Please help him find one.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 100$, $1 \le m \le 50$) — the number of strings and the length of each string.

Next $n$ lines contain a string of length $m$ each, consisting of lowercase Latin letters only. All strings are distinct.


-----Output-----

In the first line, print the length of the longest palindrome string you made.

In the second line, print that palindrome. If there are multiple answers, print any one of them. If the palindrome is empty, print an empty line or don't print this line at all.


-----Examples-----
Input
3 3
tab
one
bat

Output
6
tabbat

Input
4 2
oo
ox
xo
xx

Output
6
oxxxxo

Input
3 5
hello
codef
orces

Output
0


Input
9 4
abab
baba
abcd
bcde
cdef
defg
wxyz
zyxw
ijji

Output
20
ababwxyzijjizyxwbaba



-----Note-----

In the first example, "battab" is also a valid answer.

In the second example, there can be 4 different valid answers including the sample output. We are not going to provide any hints for what the others are.

In the third example, the empty string is the only valid palindrome string.
user: Let's call a list of positive integers $a_0, a_1, ..., a_{n-1}$ a power sequence if there is a positive integer $c$, so that for every $0 \le i \le n-1$ then $a_i = c^i$.

Given a list of $n$ positive integers $a_0, a_1, ..., a_{n-1}$, you are allowed to:  Reorder the list (i.e. pick a permutation $p$ of $\{0,1,...,n - 1\}$ and change $a_i$ to $a_{p_i}$), then  Do the following operation any number of times: pick an index $i$ and change $a_i$ to $a_i - 1$ or $a_i + 1$ (i.e. increment or decrement $a_i$ by $1$) with a cost of $1$. 

Find the minimum cost to transform $a_0, a_1, ..., a_{n-1}$ into a power sequence.


-----Input-----

The first line contains an integer $n$ ($3 \le n \le 10^5$).

The second line contains $n$ integers $a_0, a_1, ..., a_{n-1}$ ($1 \le a_i \le 10^9$).


-----Output-----

Print the minimum cost to transform $a_0, a_1, ..., a_{n-1}$ into a power sequence.


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

Output
1

Input
3
1000000000 1000000000 1000000000

Output
1999982505



-----Note-----

In the first example, we first reorder $\{1, 3, 2\}$ into $\{1, 2, 3\}$, then increment $a_2$ to $4$ with cost $1$ to get a power sequence $\{1, 2, 4\}$.
user: Lord Omkar has permitted you to enter the Holy Church of Omkar! To test your worthiness, Omkar gives you a password which you must interpret!

A password is an array $a$ of $n$ positive integers. You apply the following operation to the array: pick any two adjacent numbers that are not equal to each other and replace them with their sum. Formally, choose an index $i$ such that $1 \leq i < n$ and $a_{i} \neq a_{i+1}$, delete both $a_i$ and $a_{i+1}$ from the array and put $a_{i}+a_{i+1}$ in their place. 

For example, for array $[7, 4, 3, 7]$ you can choose $i = 2$ and the array will become $[7, 4+3, 7] = [7, 7, 7]$. Note that in this array you can't apply this operation anymore.

Notice that one operation will decrease the size of the password by $1$. What is the shortest possible length of the password after some number (possibly $0$) of operations?


-----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 each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the password.

The second line of each test case contains $n$ integers $a_{1},a_{2},\dots,a_{n}$ ($1 \leq a_{i} \leq 10^9$) — the initial contents of your password.

The sum of $n$ over all test cases will not exceed $2 \cdot 10^5$.


-----Output-----

For each password, print one integer: the shortest possible length of the password after some number of operations.


-----Example-----
Input
2
4
2 1 3 1
2
420 420

Output
1
2



-----Note-----

In the first test case, you can do the following to achieve a length of $1$:

Pick $i=2$ to get $[2, 4, 1]$

Pick $i=1$ to get $[6, 1]$

Pick $i=1$ to get $[7]$

In the second test case, you can't perform any operations because there is no valid $i$ that satisfies the requirements mentioned above.
user: Student Dima from Kremland has a matrix $a$ of size $n \times m$ filled with non-negative integers.

He wants to select exactly one integer from each row of the matrix so that the bitwise exclusive OR of the selected integers is strictly greater than zero. Help him!

Formally, he wants to choose an integers sequence $c_1, c_2, \ldots, c_n$ ($1 \leq c_j \leq m$) so that the inequality $a_{1, c_1} \oplus a_{2, c_2} \oplus \ldots \oplus a_{n, c_n} > 0$ holds, where $a_{i, j}$ is the matrix element from the $i$-th row and the $j$-th column.

Here $x \oplus y$ denotes the bitwise XOR operation of integers $x$ and $y$.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 500$) — the number of rows and the number of columns in the matrix $a$.

Each of the next $n$ lines contains $m$ integers: the $j$-th integer in the $i$-th line is the $j$-th element of the $i$-th row of the matrix $a$, i.e. $a_{i, j}$ ($0 \leq a_{i, j} \leq 1023$). 


-----Output-----

If there is no way to choose one integer from each row so that their bitwise exclusive OR is strictly greater than zero, print "NIE".

Otherwise print "TAK" in the first line, in the next line print $n$ integers $c_1, c_2, \ldots c_n$ ($1 \leq c_j \leq m$), so that the inequality $a_{1, c_1} \oplus a_{2, c_2} \oplus \ldots \oplus a_{n, c_n} > 0$ holds. 

If there is more than one possible answer, you may output any.


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

Output
NIE

Input
2 3
7 7 7
7 7 10

Output
TAK
1 3 



-----Note-----

In the first example, all the numbers in the matrix are $0$, so it is impossible to select one number in each row of the table so that their bitwise exclusive OR is strictly greater than zero.

In the second example, the selected numbers are $7$ (the first number in the first line) and $10$ (the third number in the second line), $7 \oplus 10 = 13$, $13$ is more than $0$, so the answer is found.
user: Given are two strings s and t consisting of lowercase English letters. Determine if there exists an integer i satisfying the following condition, and find the minimum such i if it exists.
 - Let s' be the concatenation of 10^{100} copies of s. t is a subsequence of the string {s'}_1{s'}_2\ldots{s'}_i (the first i characters in s').

-----Notes-----
 - A subsequence of a string a is a string obtained by deleting zero or more characters from a and concatenating the remaining characters without changing the relative order. For example, the subsequences of contest include net, c, and contest.

-----Constraints-----
 - 1 \leq |s| \leq 10^5
 - 1 \leq |t| \leq 10^5
 - s and t consists of lowercase English letters.

-----Input-----
Input is given from Standard Input in the following format:
s
t

-----Output-----
If there exists an integer i satisfying the following condition, print the minimum such i; otherwise, print -1.

-----Sample Input-----
contest
son

-----Sample Output-----
10

t = son is a subsequence of the string contestcon (the first 10 characters in s' = contestcontestcontest...), so i = 10 satisfies the condition.
On the other hand, t is not a subsequence of the string contestco (the first 9 characters in s'), so i = 9 does not satisfy the condition.
Similarly, any integer less than 9 does not satisfy the condition, either. Thus, the minimum integer i satisfying the condition is 10.
user: Bear Limak examines a social network. Its main functionality is that two members can become friends (then they can talk with each other and share funny pictures).

There are n members, numbered 1 through n. m pairs of members are friends. Of course, a member can't be a friend with themselves.

Let A-B denote that members A and B are friends. Limak thinks that a network is reasonable if and only if the following condition is satisfied: For every three distinct members (X, Y, Z), if X-Y and Y-Z then also X-Z.

For example: if Alan and Bob are friends, and Bob and Ciri are friends, then Alan and Ciri should be friends as well.

Can you help Limak and check if the network is reasonable? Print "YES" or "NO" accordingly, without the quotes.


-----Input-----

The first line of the input contain two integers n and m (3 ≤ n ≤ 150 000, $0 \leq m \leq \operatorname{min}(150000, \frac{n \cdot(n - 1)}{2})$) — the number of members and the number of pairs of members that are friends.

The i-th of the next m lines contains two distinct integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}). Members a_{i} and b_{i} are friends with each other. No pair of members will appear more than once in the input.


-----Output-----

If the given network is reasonable, print "YES" in a single line (without the quotes). Otherwise, print "NO" in a single line (without the quotes).


-----Examples-----
Input
4 3
1 3
3 4
1 4

Output
YES

Input
4 4
3 1
2 3
3 4
1 2

Output
NO

Input
10 4
4 3
5 10
8 9
1 2

Output
YES

Input
3 2
1 2
2 3

Output
NO



-----Note-----

The drawings below show the situation in the first sample (on the left) and in the second sample (on the right). Each edge represents two members that are friends. The answer is "NO" in the second sample because members (2, 3) are friends and members (3, 4) are friends, while members (2, 4) are not.

 [Image]
user: [Image] 


-----Input-----

The first line of the input is a string (between 1 and 50 characters long, inclusive). Each character will be a letter of English alphabet, lowercase or uppercase.

The second line of the input is an integer between 0 and 26, inclusive.


-----Output-----

Output the required string.


-----Examples-----
Input
AprilFool
14

Output
AprILFooL
user: Yaroslav, Andrey and Roman can play cubes for hours and hours. But the game is for three, so when Roman doesn't show up, Yaroslav and Andrey play another game. 

Roman leaves a word for each of them. Each word consists of 2·n binary characters "0" or "1". After that the players start moving in turns. Yaroslav moves first. During a move, a player must choose an integer from 1 to 2·n, which hasn't been chosen by anybody up to that moment. Then the player takes a piece of paper and writes out the corresponding character from his string. 

Let's represent Yaroslav's word as s = s_1s_2... s_2n. Similarly, let's represent Andrey's word as t = t_1t_2... t_2n. Then, if Yaroslav choose number k during his move, then he is going to write out character s_{k} on the piece of paper. Similarly, if Andrey choose number r during his move, then he is going to write out character t_{r} on the piece of paper.

The game finishes when no player can make a move. After the game is over, Yaroslav makes some integer from the characters written on his piece of paper (Yaroslav can arrange these characters as he wants). Andrey does the same. The resulting numbers can contain leading zeroes. The person with the largest number wins. If the numbers are equal, the game ends with a draw.

You are given two strings s and t. Determine the outcome of the game provided that Yaroslav and Andrey play optimally well.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^6). The second line contains string s — Yaroslav's word. The third line contains string t — Andrey's word.

It is guaranteed that both words consist of 2·n characters "0" and "1".


-----Output-----

Print "First", if both players play optimally well and Yaroslav wins. If Andrey wins, print "Second" and if the game ends with a draw, print "Draw". Print the words without the quotes.


-----Examples-----
Input
2
0111
0001

Output
First

Input
3
110110
001001

Output
First

Input
3
111000
000111

Output
Draw

Input
4
01010110
00101101

Output
First

Input
4
01100000
10010011

Output
Second
user: Grigoriy, like the hero of one famous comedy film, found a job as a night security guard at the museum. At first night he received embosser and was to take stock of the whole exposition.

Embosser is a special devise that allows to "print" the text of a plastic tape. Text is printed sequentially, character by character. The device consists of a wheel with a lowercase English letters written in a circle, static pointer to the current letter and a button that print the chosen letter. At one move it's allowed to rotate the alphabetic wheel one step clockwise or counterclockwise. Initially, static pointer points to letter 'a'. Other letters are located as shown on the picture: [Image] 

After Grigoriy add new item to the base he has to print its name on the plastic tape and attach it to the corresponding exhibit. It's not required to return the wheel to its initial position with pointer on the letter 'a'.

Our hero is afraid that some exhibits may become alive and start to attack him, so he wants to print the names as fast as possible. Help him, for the given string find the minimum number of rotations of the wheel required to print it.


-----Input-----

The only line of input contains the name of some exhibit — the non-empty string consisting of no more than 100 characters. It's guaranteed that the string consists of only lowercase English letters.


-----Output-----

Print one integer — the minimum number of rotations of the wheel, required to print the name given in the input.


-----Examples-----
Input
zeus

Output
18

Input
map

Output
35

Input
ares

Output
34



-----Note-----

  [Image] 

To print the string from the first sample it would be optimal to perform the following sequence of rotations:   from 'a' to 'z' (1 rotation counterclockwise),  from 'z' to 'e' (5 clockwise rotations),  from 'e' to 'u' (10 rotations counterclockwise),  from 'u' to 's' (2 counterclockwise rotations).  In total, 1 + 5 + 10 + 2 = 18 rotations are required.
user: The final match of the Berland Football Cup has been held recently. The referee has shown $n$ yellow cards throughout the match. At the beginning of the match there were $a_1$ players in the first team and $a_2$ players in the second team.

The rules of sending players off the game are a bit different in Berland football. If a player from the first team receives $k_1$ yellow cards throughout the match, he can no longer participate in the match — he's sent off. And if a player from the second team receives $k_2$ yellow cards, he's sent off. After a player leaves the match, he can no longer receive any yellow cards. Each of $n$ yellow cards was shown to exactly one player. Even if all players from one team (or even from both teams) leave the match, the game still continues.

The referee has lost his records on who has received each yellow card. Help him to determine the minimum and the maximum number of players that could have been thrown out of the game.


-----Input-----

The first line contains one integer $a_1$ $(1 \le a_1 \le 1\,000)$ — the number of players in the first team.

The second line contains one integer $a_2$ $(1 \le a_2 \le 1\,000)$ — the number of players in the second team.

The third line contains one integer $k_1$ $(1 \le k_1 \le 1\,000)$ — the maximum number of yellow cards a player from the first team can receive (after receiving that many yellow cards, he leaves the game).

The fourth line contains one integer $k_2$ $(1 \le k_2 \le 1\,000)$ — the maximum number of yellow cards a player from the second team can receive (after receiving that many yellow cards, he leaves the game).

The fifth line contains one integer $n$ $(1 \le n \le a_1 \cdot k_1 + a_2 \cdot k_2)$ — the number of yellow cards that have been shown during the match.


-----Output-----

Print two integers — the minimum and the maximum number of players that could have been thrown out of the game.


-----Examples-----
Input
2
3
5
1
8

Output
0 4

Input
3
1
6
7
25

Output
4 4

Input
6
4
9
10
89

Output
5 9



-----Note-----

In the first example it could be possible that no player left the game, so the first number in the output is $0$. The maximum possible number of players that could have been forced to leave the game is $4$ — one player from the first team, and three players from the second.

In the second example the maximum possible number of yellow cards has been shown $(3 \cdot 6 + 1 \cdot 7 = 25)$, so in any case all players were sent off.
user: During the break the schoolchildren, boys and girls, formed a queue of n people in the canteen. Initially the children stood in the order they entered the canteen. However, after a while the boys started feeling awkward for standing in front of the girls in the queue and they started letting the girls move forward each second. 

Let's describe the process more precisely. Let's say that the positions in the queue are sequentially numbered by integers from 1 to n, at that the person in the position number 1 is served first. Then, if at time x a boy stands on the i-th position and a girl stands on the (i + 1)-th position, then at time x + 1 the i-th position will have a girl and the (i + 1)-th position will have a boy. The time is given in seconds.

You've got the initial position of the children, at the initial moment of time. Determine the way the queue is going to look after t seconds.


-----Input-----

The first line contains two integers n and t (1 ≤ n, t ≤ 50), which represent the number of children in the queue and the time after which the queue will transform into the arrangement you need to find. 

The next line contains string s, which represents the schoolchildren's initial arrangement. If the i-th position in the queue contains a boy, then the i-th character of string s equals "B", otherwise the i-th character equals "G".


-----Output-----

Print string a, which describes the arrangement after t seconds. If the i-th position has a boy after the needed time, then the i-th character a must equal "B", otherwise it must equal "G".


-----Examples-----
Input
5 1
BGGBG

Output
GBGGB

Input
5 2
BGGBG

Output
GGBGB

Input
4 1
GGGB

Output
GGGB
user: Makoto has a big blackboard with a positive integer $n$ written on it. He will perform the following action exactly $k$ times:

Suppose the number currently written on the blackboard is $v$. He will randomly pick one of the divisors of $v$ (possibly $1$ and $v$) and replace $v$ with this divisor. As Makoto uses his famous random number generator (RNG) and as he always uses $58$ as his generator seed, each divisor is guaranteed to be chosen with equal probability.

He now wonders what is the expected value of the number written on the blackboard after $k$ steps.

It can be shown that this value can be represented as $\frac{P}{Q}$ where $P$ and $Q$ are coprime integers and $Q \not\equiv 0 \pmod{10^9+7}$. Print the value of $P \cdot Q^{-1}$ modulo $10^9+7$.


-----Input-----

The only line of the input contains two integers $n$ and $k$ ($1 \leq n \leq 10^{15}$, $1 \leq k \leq 10^4$).


-----Output-----

Print a single integer — the expected value of the number on the blackboard after $k$ steps as $P \cdot Q^{-1} \pmod{10^9+7}$ for $P$, $Q$ defined above.


-----Examples-----
Input
6 1

Output
3

Input
6 2

Output
875000008

Input
60 5

Output
237178099



-----Note-----

In the first example, after one step, the number written on the blackboard is $1$, $2$, $3$ or $6$ — each occurring with equal probability. Hence, the answer is $\frac{1+2+3+6}{4}=3$.

In the second example, the answer is equal to $1 \cdot \frac{9}{16}+2 \cdot \frac{3}{16}+3 \cdot \frac{3}{16}+6 \cdot \frac{1}{16}=\frac{15}{8}$.
user: Now it's time of Olympiads. Vanya and Egor decided to make his own team to take part in a programming Olympiad. They've been best friends ever since primary school and hopefully, that can somehow help them in teamwork.

For each team Olympiad, Vanya takes his play cards with numbers. He takes only the cards containing numbers 1 and 0. The boys are very superstitious. They think that they can do well at the Olympiad if they begin with laying all the cards in a row so that:  there wouldn't be a pair of any side-adjacent cards with zeroes in a row;  there wouldn't be a group of three consecutive cards containing numbers one. 

Today Vanya brought n cards with zeroes and m cards with numbers one. The number of cards was so much that the friends do not know how to put all those cards in the described way. Help them find the required arrangement of the cards or else tell the guys that it is impossible to arrange cards in such a way.


-----Input-----

The first line contains two integers: n (1 ≤ n ≤ 10^6) — the number of cards containing number 0; m (1 ≤ m ≤ 10^6) — the number of cards containing number 1.


-----Output-----

In a single line print the required sequence of zeroes and ones without any spaces. If such sequence is impossible to obtain, print -1.


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

Output
101

Input
4 8

Output
110110110101

Input
4 10

Output
11011011011011

Input
1 5

Output
-1