meetforever/GRPO_CL huggingface dataset:
user: Polygon is not only the best platform for developing problems but also a square matrix with side $n$, initially filled with the character 0.

On the polygon, military training was held. The soldiers placed a cannon above each cell in the first row and a cannon to the left of each cell in the first column. Thus, exactly $2n$ cannons were placed. [Image] Initial polygon for $n=4$. 

Cannons shoot character 1. At any moment of time, no more than one cannon is shooting. When a 1 flies out of a cannon, it flies forward (in the direction of the shot) until it collides with a polygon border or another 1. After that, it takes the cell in which it was before the collision and remains there. Take a look at the examples for better understanding.

More formally:   if a cannon stands in the row $i$, to the left of the first column, and shoots with a 1, then the 1 starts its flight from the cell ($i, 1$) and ends in some cell ($i, j$);  if a cannon stands in the column $j$, above the first row, and shoots with a 1, then the 1 starts its flight from the cell ($1, j$) and ends in some cell ($i, j$). 

For example, consider the following sequence of shots: [Image] 

 1. Shoot the cannon in the row $2$.                         2. Shoot the cannon in the row $2$.                         3. Shoot the cannon in column $3$. 

You have a report from the military training on your desk. This report is a square matrix with side length $n$ consisting of 0 and 1. You wonder if the training actually happened. In other words, is there a sequence of shots such that, after the training, you get the given matrix?

Each cannon can make an arbitrary number of shots. Before the training, each cell of the polygon contains 0.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then $t$ test cases follow.

Each test case starts with a line containing an integer $n$ ($1 \le n \le 50$) — the size of the polygon.

This is followed by $n$ lines of length $n$, consisting of 0 and 1 — the polygon matrix after the training.

The total area of the matrices in all test cases in one test does not exceed $10^5$.


-----Output-----

For each test case print:  YES if there is a sequence of shots leading to a given matrix;  NO if such a sequence does not exist. 

The letters in the words YES and NO can be printed in any case.


-----Example-----
Input
5
4
0010
0011
0000
0000
2
10
01
2
00
00
4
0101
1111
0101
0111
4
0100
1110
0101
0111

Output
YES
NO
YES
YES
NO



-----Note-----

The first test case was explained in the statement.

The answer to the second test case is NO, since a 1 in a cell ($1, 1$) flying out of any cannon would continue its flight further.
user: You are given a bracket sequence $s$ of length $n$, where $n$ is even (divisible by two). The string $s$ consists of $\frac{n}{2}$ opening brackets '(' and $\frac{n}{2}$ closing brackets ')'.

In one move, you can choose exactly one bracket and move it to the beginning of the string or to the end of the string (i.e. you choose some index $i$, remove the $i$-th character of $s$ and insert it before or after all remaining characters of $s$).

Your task is to find the minimum number of moves required to obtain regular bracket sequence from $s$. It can be proved that the answer always exists under the given constraints.

Recall what the regular bracket sequence is:

  "()" is regular bracket sequence;  if $s$ is regular bracket sequence then "(" + $s$ + ")" is regular bracket sequence;  if $s$ and $t$ are regular bracket sequences then $s$ + $t$ is regular bracket sequence. 

For example, "()()", "(())()", "(())" and "()" are regular bracket sequences, but ")(", "()(" and ")))" are not.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2000$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($2 \le n \le 50$) — the length of $s$. It is guaranteed that $n$ is even. The second line of the test case containg the string $s$ consisting of $\frac{n}{2}$ opening and $\frac{n}{2}$ closing brackets.


-----Output-----

For each test case, print the answer — the minimum number of moves required to obtain regular bracket sequence from $s$. It can be proved that the answer always exists under the given constraints.


-----Example-----
Input
4
2
)(
4
()()
8
())()()(
10
)))((((())

Output
1
0
1
3



-----Note-----

In the first test case of the example, it is sufficient to move the first bracket to the end of the string.

In the third test case of the example, it is sufficient to move the last bracket to the beginning of the string.

In the fourth test case of the example, we can choose last three openning brackets, move them to the beginning of the string and obtain "((()))(())".
user: A number is ternary if it contains only digits $0$, $1$ and $2$. For example, the following numbers are ternary: $1022$, $11$, $21$, $2002$.

You are given a long ternary number $x$. The first (leftmost) digit of $x$ is guaranteed to be $2$, the other digits of $x$ can be $0$, $1$ or $2$.

Let's define the ternary XOR operation $\odot$ of two ternary numbers $a$ and $b$ (both of length $n$) as a number $c = a \odot b$ of length $n$, where $c_i = (a_i + b_i) \% 3$ (where $\%$ is modulo operation). In other words, add the corresponding digits and take the remainders of the sums when divided by $3$. For example, $10222 \odot 11021 = 21210$.

Your task is to find such ternary numbers $a$ and $b$ both of length $n$ and both without leading zeros that $a \odot b = x$ and $max(a, b)$ is the minimum possible.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow. The first line of the test case contains one integer $n$ ($1 \le n \le 5 \cdot 10^4$) — the length of $x$. The second line of the test case contains ternary number $x$ consisting of $n$ digits $0, 1$ or $2$. It is guaranteed that the first digit of $x$ is $2$. It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^4$ ($\sum n \le 5 \cdot 10^4$).


-----Output-----

For each test case, print the answer — two ternary integers $a$ and $b$ both of length $n$ and both without leading zeros such that $a \odot b = x$ and $max(a, b)$ is the minimum possible. If there are several answers, you can print any.


-----Example-----
Input
4
5
22222
5
21211
1
2
9
220222021

Output
11111
11111
11000
10211
1
1
110111011
110111010
user: You are given a string $s[1 \dots n]$ consisting of lowercase Latin letters. It is guaranteed that $n = 2^k$ for some integer $k \ge 0$.

The string $s[1 \dots n]$ is called $c$-good if at least one of the following three conditions is satisfied:  The length of $s$ is $1$, and it consists of the character $c$ (i.e. $s_1=c$); The length of $s$ is greater than $1$, the first half of the string consists of only the character $c$ (i.e. $s_1=s_2=\dots=s_{\frac{n}{2}}=c$) and the second half of the string (i.e. the string $s_{\frac{n}{2} + 1}s_{\frac{n}{2} + 2} \dots s_n$) is a $(c+1)$-good string;  The length of $s$ is greater than $1$, the second half of the string consists of only the character $c$ (i.e. $s_{\frac{n}{2} + 1}=s_{\frac{n}{2} + 2}=\dots=s_n=c$) and the first half of the string (i.e. the string $s_1s_2 \dots s_{\frac{n}{2}}$) is a $(c+1)$-good string. 

For example: "aabc" is 'a'-good, "ffgheeee" is 'e'-good.

In one move, you can choose one index $i$ from $1$ to $n$ and replace $s_i$ with any lowercase Latin letter (any character from 'a' to 'z').

Your task is to find the minimum number of moves required to obtain an 'a'-good string from $s$ (i.e. $c$-good string for $c=$ 'a'). It is guaranteed that the answer always exists.

You have to answer $t$ independent test cases.

Another example of an 'a'-good string is as follows. Consider the string $s = $"cdbbaaaa". It is an 'a'-good string, because:  the second half of the string ("aaaa") consists of only the character 'a';  the first half of the string ("cdbb") is 'b'-good string, because:   the second half of the string ("bb") consists of only the character 'b';  the first half of the string ("cd") is 'c'-good string, because:   the first half of the string ("c") consists of only the character 'c';  the second half of the string ("d") is 'd'-good string.   


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 131~072$) — the length of $s$. It is guaranteed that $n = 2^k$ for some integer $k \ge 0$. The second line of the test case contains the string $s$ consisting of $n$ lowercase Latin letters.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer — the minimum number of moves required to obtain an 'a'-good string from $s$ (i.e. $c$-good string with $c =$ 'a'). It is guaranteed that the answer exists.


-----Example-----
Input
6
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z
2
ac

Output
0
7
4
5
1
1
user: Consider all binary strings of length $m$ ($1 \le m \le 60$). A binary string is a string that consists of the characters 0 and 1 only. For example, 0110 is a binary string, and 012aba is not. Obviously, there are exactly $2^m$ such strings in total.

The string $s$ is lexicographically smaller than the string $t$ (both have the same length $m$) if in the first position $i$ from the left in which they differ, we have $s[i] < t[i]$. This is exactly the way strings are compared in dictionaries and in most modern programming languages when comparing them in a standard way. For example, the string 01011 is lexicographically smaller than the string 01100, because the first two characters are the same, and the third character in the first string is less than that in the second.

We remove from this set $n$ ($1 \le n \le \min(2^m-1, 100)$) distinct binary strings $a_1, a_2, \ldots, a_n$, each of length $m$. Thus, the set will have $k=2^m-n$ strings. Sort all strings of the resulting set in lexicographical ascending order (as in the dictionary).

We number all the strings after sorting from $0$ to $k-1$. Print the string whose index is $\lfloor \frac{k-1}{2} \rfloor$ (such an element is called median), where $\lfloor x \rfloor$ is the rounding of the number down to the nearest integer.

For example, if $n=3$, $m=3$ and $a=[$010, 111, 001$]$, then after removing the strings $a_i$ and sorting, the result will take the form: $[$000, 011, 100, 101, 110$]$. Thus, the desired median is 100.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then, $t$ test cases follow.

The first line of each test case contains integers $n$ ($1 \le n \le \min(2^m-1, 100)$) and $m$ ($1 \le m \le 60$), where $n$ is the number of strings to remove, and $m$ is the length of binary strings. The next $n$ lines contain $a_1, a_2, \ldots, a_n$ — distinct binary strings of length $m$.

The total length of all given binary strings in all test cases in one test does not exceed $10^5$.


-----Output-----

Print $t$ answers to the test cases. For each test case, print a string of length $m$ — the median of the sorted sequence of remaining strings in the corresponding test case.


-----Example-----
Input
5
3 3
010
001
111
4 3
000
111
100
011
1 1
1
1 1
0
3 2
00
01
10

Output
100
010
0
1
11



-----Note-----

The first test case is explained in the statement.

In the second test case, the result after removing strings and sorting is $[$001, 010, 101, 110$]$. Therefore, the desired median is 010.
user: You are given a table $a$ of size $2 \times n$ (i.e. two rows and $n$ columns) consisting of integers from $1$ to $n$.

In one move, you can choose some column $j$ ($1 \le j \le n$) and swap values $a_{1, j}$ and $a_{2, j}$ in it. Each column can be chosen no more than once.

Your task is to find the minimum number of moves required to obtain permutations of size $n$ in both first and second rows of the table or determine if it is impossible to do that.

You have to answer $t$ independent test cases.

Recall that the permutation of size $n$ is such an array of size $n$ that contains each integer from $1$ to $n$ exactly once (the order of elements doesn't matter).


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of columns in the table. The second line of the test case contains $n$ integers $a_{1, 1}, a_{1, 2}, \dots, a_{1, n}$ ($1 \le a_{1, i} \le n$), where $a_{1, i}$ is the $i$-th element of the first row of the table. The third line of the test case contains $n$ integers $a_{2, 1}, a_{2, 2}, \dots, a_{2, n}$ ($1 \le a_{2, i} \le n$), where $a_{2, i}$ is the $i$-th element of the second row of the table.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case print the answer: -1 if it is impossible to obtain permutation of size $n$ in both first and the second rows of the table, or one integer $k$ in the first line, where $k$ is the minimum number of moves required to obtain permutations in both rows, and $k$ distinct integers $pos_1, pos_2, \dots, pos_k$ in the second line ($1 \le pos_i \le n$) in any order — indices of columns in which you need to swap values to obtain permutations in both rows. If there are several answers, you can print any.


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

Output
0

2
2 3 
1
1 
2
3 4 
2
3 4 
-1
user: You are given a graph consisting of $n$ vertices and $m$ edges. It is not guaranteed that the given graph is connected. Some edges are already directed and you can't change their direction. Other edges are undirected and you have to choose some direction for all these edges.

You have to direct undirected edges in such a way that the resulting graph is directed and acyclic (i.e. the graph with all edges directed and having no directed cycles). Note that you have to direct all undirected edges.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2})$) — the number of vertices and the number of edges in the graph, respectively.

The next $m$ lines describe edges of the graph. The $i$-th edge is described with three integers $t_i$, $x_i$ and $y_i$ ($t_i \in [0; 1]$, $1 \le x_i, y_i \le n$) — the type of the edge ($t_i = 0$ if the edge is undirected and $t_i = 1$ if the edge is directed) and vertices this edge connects (the undirected edge connects vertices $x_i$ and $y_i$ and directed edge is going from the vertex $x_i$ to the vertex $y_i$). It is guaranteed that the graph do not contain self-loops (i.e. edges from the vertex to itself) and multiple edges (i.e. for each pair ($x_i, y_i$) there are no other pairs ($x_i, y_i$) or ($y_i, x_i$)).

It is guaranteed that both sum $n$ and sum $m$ do not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$; $\sum m \le 2 \cdot 10^5$).


-----Output-----

For each test case print the answer — "NO" if it is impossible to direct undirected edges in such a way that the resulting graph is directed and acyclic, otherwise print "YES" on the first line and $m$ lines describing edges of the resulted directed acyclic graph (in any order). Note that you cannot change the direction of the already directed edges. If there are several answers, you can print any.


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

Output
YES
3 1
YES
2 1
1 5
5 4
2 5
3 5
YES
1 2
3 4
3 1
3 2
2 4
NO



-----Note-----

Explanation of the second test case of the example:

[Image]

Explanation of the third test case of the example:

[Image]
user: The round carousel consists of $n$ figures of animals. Figures are numbered from $1$ to $n$ in order of the carousel moving. Thus, after the $n$-th figure the figure with the number $1$ follows. Each figure has its own type — the type of the animal corresponding to this figure (the horse, the tiger and so on). The type of animal of the $i$-th figure equals $t_i$. [Image] The example of the carousel for $n=9$ and $t=[5, 5, 1, 15, 1, 5, 5, 1, 1]$. 

You want to color each figure in one of the colors. You think that it's boring if the carousel contains two different figures (with the distinct types of animals) going one right after another and colored in the same color.

Your task is to color the figures in such a way that the number of distinct colors used is the minimum possible and there are no figures of the different types going one right after another and colored in the same color. If you use exactly $k$ distinct colors, then the colors of figures should be denoted with integers from $1$ to $k$.


-----Input-----

The input contains one or more test cases.

The first line contains one integer $q$ ($1 \le q \le 10^4$) — the number of test cases in the test. Then $q$ test cases follow. One test case is given on two lines.

The first line of the test case contains one integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of figures in the carousel. Figures are numbered from $1$ to $n$ in order of carousel moving. Assume that after the $n$-th figure the figure $1$ goes.

The second line of the test case contains $n$ integers $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 2 \cdot 10^5$), where $t_i$ is the type of the animal of the $i$-th figure.

The sum of $n$ over all test cases does not exceed $2\cdot10^5$.


-----Output-----

Print $q$ answers, for each test case print two lines.

In the first line print one integer $k$ — the minimum possible number of distinct colors of figures.

In the second line print $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le k$), where $c_i$ is the color of the $i$-th figure. If there are several answers, you can print any.


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

Output
2
1 2 1 2 2
2
2 1 2 1 2 1
3
2 3 2 3 1
1
1 1 1
user: Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Example 1:


Input: pattern = "abba", str = "dog cat cat dog"
Output: true

Example 2:


Input:pattern = "abba", str = "dog cat cat fish"
Output: false

Example 3:


Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false

Example 4:


Input: pattern = "abba", str = "dog dog dog dog"
Output: false

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Answer: {"fn_name": "wordPattern", "inputs": [["\"abba\"", "\"dog cat cat dog\""]], "outputs": [false]}
user: Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"



Note:
In the string, each word is separated by single space and there will not be any extra space in the string.

Answer: {"fn_name": "reverseWords", "inputs": [["\"Let's take LeetCode contest\""]], "outputs": ["s'teL\" ekat edoCteeL \"tsetnoc"]}
user: We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself. 

Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.


Example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14



Note:
The input number n will not exceed 100,000,000. (1e8)

Answer: {"fn_name": "checkPerfectNumber", "inputs": [[28]], "outputs": [true]}
user: Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Find the kth positive integer that is missing from this array.
 
Example 1:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2:
Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

 
Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length

Answer: {"fn_name": "findKthPositive", "inputs": [[[2, 3, 4, 7, 11], 5]], "outputs": [9]}
user: A robot on an infinite grid starts at point (0, 0) and faces north.  The robot can receive one of three possible types of commands:

-2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units

Some of the grid squares are obstacles. 
The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])
If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)
Return the square of the maximum Euclidean distance that the robot will be from the origin.
 
Example 1:
Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)


Example 2:
Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)


 
Note:

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
The answer is guaranteed to be less than 2 ^ 31.

Answer: {"fn_name": "robotSim", "inputs": [[[4, -1, 3], [[], []]]], "outputs": [25]}
user: Let's call an array arr a mountain if the following properties hold:

arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
        
arr[0] < arr[1] < ... arr[i-1] < arr[i] 
arr[i] > arr[i+1] > ... > arr[arr.length - 1]



Given an integer array arr that is guaranteed to be a mountain, return any i such that arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].
 
Example 1:
Input: arr = [0,1,0]
Output: 1
Example 2:
Input: arr = [0,2,1,0]
Output: 1
Example 3:
Input: arr = [0,10,5,2]
Output: 1
Example 4:
Input: arr = [3,4,5,1]
Output: 2
Example 5:
Input: arr = [24,69,100,99,79,78,67,36,26,19]
Output: 2

 
Constraints:

3 <= arr.length <= 104
0 <= arr[i] <= 106
arr is guaranteed to be a mountain array.

Answer: {"fn_name": "peakIndexInMountainArray", "inputs": [[[0, 1, 0]]], "outputs": [1]}
user: Given an integer number n, return the difference between the product of its digits and the sum of its digits.
 
Example 1:
Input: n = 234
Output: 15 
Explanation: 
Product of digits = 2 * 3 * 4 = 24 
Sum of digits = 2 + 3 + 4 = 9 
Result = 24 - 9 = 15

Example 2:
Input: n = 4421
Output: 21
Explanation: 
Product of digits = 4 * 4 * 2 * 1 = 32 
Sum of digits = 4 + 4 + 2 + 1 = 11 
Result = 32 - 11 = 21

 
Constraints:

1 <= n <= 10^5

Answer: {"fn_name": "subtractProductAndSum", "inputs": [[234]], "outputs": [15]}
user: Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.




Note: You may assume the string contain only lowercase letters.

Answer: {"fn_name": "firstUniqChar", "inputs": [["\"leetcode\""]], "outputs": [1]}