vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Sasha likes programming. Once, during a very long contest, Sasha decided that he was a bit tired and needed to relax. So he did. But since Sasha isn't an ordinary guy, he prefers to relax unusually. During leisure time Sasha likes to upsolve unsolved problems because upsolving is very useful.

Therefore, Sasha decided to upsolve the following problem:

You have an array $a$ with $n$ integers. You need to count the number of funny pairs $(l, r)$ $(l \leq r)$. To check if a pair $(l, r)$ is a funny pair, take $mid = \frac{l + r - 1}{2}$, then if $r - l + 1$ is an even number and $a_l \oplus a_{l+1} \oplus \ldots \oplus a_{mid} = a_{mid + 1} \oplus a_{mid + 2} \oplus \ldots \oplus a_r$, then the pair is funny. In other words, $\oplus$ of elements of the left half of the subarray from $l$ to $r$ should be equal to $\oplus$ of elements of the right half. Note that $\oplus$ denotes the bitwise XOR operation.

It is time to continue solving the contest, so Sasha asked you to solve this task.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 3 \cdot 10^5$) — the size of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^{20}$) — array itself.


-----Output-----

Print one integer — the number of funny pairs. You should consider only pairs where $r - l + 1$ is even number.


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

Output
1

Input
6
3 2 2 3 7 6

Output
3

Input
3
42 4 2

Output
0



-----Note-----

Be as cool as Sasha, upsolve problems!

In the first example, the only funny pair is $(2, 5)$, as $2 \oplus 3 = 4 \oplus 5 = 1$.

In the second example, funny pairs are $(2, 3)$, $(1, 4)$, and $(3, 6)$.

In the third example, there are no funny pairs.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have recently started playing a brand new computer game called "Mr. President". The game is about ruling a country, building infrastructures and developing it. 

Your country consists of N cities and M bidirectional roads connecting them. Each road has assigned a cost of its maintenance. The greatest achievement in the game is called "Great administrator" and it is given to a player who manage to have all cities in the country connected by roads in such a way that it is possible to travel between any two cities and that the sum of maintenance costs of these roads is not greater than K. 

This is very hard to accomplish, but you are very close to do it. More precisely, you have just discovered a new method of transforming standard roads into super roads, with cost of maintenance just 1, due to their extreme durability. 

The bad news is that it is very expensive to transform a standard road into a super road, but you are so excited that you are going to do it anyway. 

In addition, because you have a lot of other expenses, you also want to first demolish as many roads as possible in order to safe some money on their maintenance first and then start working on getting the achievement. You can demolish any road in the country and that operation does not cost you anything. 

Because you want to spend the absolutely minimum money in order to get the achievement, you are interested in the smallest number of transformations of standard roads into super roads in such a way that you can do that.

Input format:

In the first line there are 3 integers N, M and K denoting the number of cities in the country, the number of roads in it and the desired sum of costs of maintenance.
M lines describing these roads follow. In each of them there are 3 integers A, B and C, where A and B denote the endpoints of the road while C denotes the cost of its maintenance.

Output:

In a single line, output the minimum number of roads which need to be transformed in order to get the achievement. If you cannot do it no matter what, output -1.

Constraints:

2 ≤ N, M ≤ 10^6
0 ≤ K ≤ 10^18
1 ≤ A, B ≤ N and A != B
1 ≤ C ≤ 10^6

SAMPLE INPUT
3 3 25
1 2 10
2 3 20
3 1 30

SAMPLE OUTPUT
1

Explanation

You can transform to super a road either the road between cities 1 and 2 or the road between cities 2 and 3 in order to produce the desired road network of costs respectively 21 and 11. Doing that will cost you one transformation and it is optimal in this case.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ friends who want to give gifts for the New Year to each other. Each friend should give exactly one gift and receive exactly one gift. The friend cannot give the gift to himself.

For each friend the value $f_i$ is known: it is either $f_i = 0$ if the $i$-th friend doesn't know whom he wants to give the gift to or $1 \le f_i \le n$ if the $i$-th friend wants to give the gift to the friend $f_i$.

You want to fill in the unknown values ($f_i = 0$) in such a way that each friend gives exactly one gift and receives exactly one gift and there is no friend who gives the gift to himself. It is guaranteed that the initial information isn't contradictory.

If there are several answers, you can print any.


-----Input-----

The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of friends.

The second line of the input contains $n$ integers $f_1, f_2, \dots, f_n$ ($0 \le f_i \le n$, $f_i \ne i$, all $f_i \ne 0$ are distinct), where $f_i$ is the either $f_i = 0$ if the $i$-th friend doesn't know whom he wants to give the gift to or $1 \le f_i \le n$ if the $i$-th friend wants to give the gift to the friend $f_i$. It is also guaranteed that there is at least two values $f_i = 0$.


-----Output-----

Print $n$ integers $nf_1, nf_2, \dots, nf_n$, where $nf_i$ should be equal to $f_i$ if $f_i \ne 0$ or the number of friend whom the $i$-th friend wants to give the gift to. All values $nf_i$ should be distinct, $nf_i$ cannot be equal to $i$. Each friend gives exactly one gift and receives exactly one gift and there is no friend who gives the gift to himself.

If there are several answers, you can print any.


-----Examples-----
Input
5
5 0 0 2 4

Output
5 3 1 2 4 

Input
7
7 0 0 1 4 0 6

Output
7 3 2 1 4 5 6 

Input
7
7 4 0 3 0 5 1

Output
7 4 2 3 6 5 1 

Input
5
2 1 0 0 0

Output
2 1 4 5 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice had a permutation p_1, p_2, …, p_n. Unfortunately, the permutation looked very boring, so she decided to change it and choose some non-overlapping subranges of this permutation and reverse them. The cost of reversing a single subrange [l, r] (elements from position l to position r, inclusive) is equal to r - l, and the cost of the operation is the sum of costs of reversing individual subranges. Alice had an integer c in mind, so she only considered operations that cost no more than c.

Then she got really bored, and decided to write down all the permutations that she could possibly obtain by performing exactly one operation on the initial permutation. Of course, Alice is very smart, so she wrote down each obtainable permutation exactly once (no matter in how many ways it can be obtained), and of course the list was sorted lexicographically.

Now Bob would like to ask Alice some questions about her list. Each question is in the following form: what is the i-th number in the j-th permutation that Alice wrote down? Since Alice is too bored to answer these questions, she asked you to help her out.

Input

The first line contains a single integer t (1 ≤ t ≤ 30) — the number of test cases.

The first line of each test case contains three integers n, c, q (1 ≤ n ≤ 3 ⋅ 10^4, 1 ≤ c ≤ 4, 1 ≤ q ≤ 3 ⋅ 10^5) — the length of the permutation, the maximum cost of the operation, and the number of queries.

The next line of each test case contains n integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n, p_i ≠ p_j if i ≠ j), describing the initial permutation.

The following q lines describe the queries. Each of them contains two integers i and j (1 ≤ i ≤ n, 1 ≤ j ≤ 10^{18}), denoting parameters of this query.

It is guaranteed that the sum of values n over all test cases does not exceed 3 ⋅ 10^5, and the sum of values q over all test cases does not exceed 3 ⋅ 10^5.

Output

For each query output the answer for this query, or -1 if j-th permutation does not exist in her list.

Examples

Input


2
3 1 9
1 2 3
1 1
2 1
3 1
1 2
2 2
3 2
1 3
2 3
3 3
6 4 4
6 5 4 3 1 2
1 1
3 14
1 59
2 6


Output


1
2
3
1
3
2
2
1
3
1
4
-1
5


Input


1
12 4 2
1 2 3 4 5 6 7 8 9 10 11 12
2 20
2 21


Output


2
2

Note

In the first test case, Alice wrote down the following permutations: [1, 2, 3], [1, 3, 2], [2, 1, 3].

Note that, for a permutation [3, 2, 1] Alice would have to reverse the whole array, and it would cost her 2, which is greater than the specified value c=1. The other two permutations can not be obtained by performing exactly one operation described in the problem statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Two Sets

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little X has *n* distinct integers: *p*1,<=*p*2,<=...,<=*p**n*. He wants to divide all of them into two sets *A* and *B*. The following two conditions must be satisfied:
 -  If number *x* belongs to set *A*, then number *a*<=-<=*x* must also belong to set *A*. -  If number *x* belongs to set *B*, then number *b*<=-<=*x* must also belong to set *B*. 
Help Little X divide the numbers into two sets or determine that it's impossible.

Input Specification:
The first line contains three space-separated integers *n*,<=*a*,<=*b* (1<=≤<=*n*<=≤<=105; 1<=≤<=*a*,<=*b*<=≤<=109). The next line contains *n* space-separated distinct integers *p*1,<=*p*2,<=...,<=*p**n* (1<=≤<=*p**i*<=≤<=109).

Output Specification:
If there is a way to divide the numbers into two sets, then print "YES" in the first line. Then print *n* integers: *b*1,<=*b*2,<=...,<=*b**n* (*b**i* equals either 0, or 1), describing the division. If *b**i* equals to 0, then *p**i* belongs to set *A*, otherwise it belongs to set *B*.

If it's impossible, print "NO" (without the quotes).

Demo Input:
['4 5 9\n2 3 4 5\n', '3 3 4\n1 2 4\n']

Demo Output:
['YES\n0 0 1 1\n', 'NO\n']

Note:
It's OK if all the numbers are in the same set, and the other one is empty.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gold Leaf is a very thin layer of gold, with a paper backing. If the paper gets folded and then unfolded, the gold leaf will stick to itself more readily than it will stick to the paper, so there will be patches of gold and patches of exposed paper. Note that the gold leaf will always stick to itself, rather than the paper. In the following example, the paper was folded along the dashed line. Notice how the gold leaf always sticks to one side or the other, never both.

Consider a crude digital image of a sheet of gold leaf. If the area covered by a pixel is mostly gold, that will be represented by a ‘#’. If it’s mostly exposed paper, it will be represented by a ‘.’. Determine where the sheet was folded. The sheet was folded exactly once, along a horizontal, vertical, or 45 degree or 135 degree diagonal line. If the fold is horizontal or vertical, it is always between rows/columns. If the fold is diagonal, then the fold goes through a diagonal line of cells, and the cells along the fold are always ‘#’.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line with two integers, $n$ and $m$ ($2 \le n, m \le 25$), where $n$ is the number of rows, and $m$ is the number of columns of the image. Each of the next $n$ lines will contain exactly $m$ characters, all of which will be either ‘#’ or ‘.’. This represents a crudely collected digital image of the sheet of gold leaf. There is guaranteed to be at least one ‘.’, and there is guaranteed to be a solution.

-----Output-----
Output a single line with four integers, indicating the places where the fold hits the edges of the paper. Output them in this order:

    r1 c1 r2 c2

where $(r1,c1)$ and $(r2,c2)$ are row/column coordinates ($r$=row, $c$=column). The top left character of the image is $(1,1)$ and the bottom right is $(n,m)$.

If the fold is horizontal or diagonal, list the left coordinates before the right. If the fold is vertical, list the top coordinates before the bottom.

If the fold is horizontal, use the coordinates above the fold. If the fold is vertical, use the coordinates to the left of the fold. If the fold is diagonal, use the coordinates of the edge pixels that the fold goes through.

If more than one fold is possible, choose the one with the smallest first coordinate, then the smallest second coordinate, then third, then fourth.

-----Examples-----
Sample Input 1:
8 10
#.#..##..#
####..####
###.##....
...#..####
....##....
.#.##..##.
##########
##########
Sample Output 1:
3 1 3 10

Sample Input 2:
5 20
###########.#.#.#.#.
###########...#.###.
##########..##.#..##
###########..#.#.##.
###########.###...#.
Sample Output 2:
1 15 5 15

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's analyze a program written on some strange programming language. The variables in this language have names consisting of $1$ to $4$ characters, and each character is a lowercase or an uppercase Latin letter, or a digit. There is an extra constraint that the first character should not be a digit.

There are four types of operations in the program, each denoted by one of the characters: $, ^, # or &.

Each line of the program has one of the following formats:   <lvalue>=<rvalue>, where <lvalue> and <rvalue> are valid variable names;  <lvalue>=<arg1><op><arg2>, where <lvalue>, <arg1> and <arg2> are valid variable names, and <op> is an operation character. 

The program is executed line-by-line, and the result of execution is stored in a variable having the name res. If res is never assigned in the program, then the result will be equal to the value of res before running the program.

Two programs are called equivalent if no matter which operations do characters $, ^, # and & denote (but, obviously, performing the same operation on the same arguments gives the same result) and which values do variables have before execution of program, the value of res after running the first program is equal to the value of res after running the second program (the programs are executed independently).

You are given a program consisting of $n$ lines. Your task is to write a program consisting of minimum possible number of lines that is equivalent to the program you are given.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 1000$) — the number of lines in the program.

Then $n$ lines follow — the program itself. Each line corresponds to the format described in the statement and has no extra whitespaces.


-----Output-----

In the first line print $k$ — the minimum number of lines in the equivalent program.

Then print $k$ lines without any whitespaces — an equivalent program having exactly $k$ lines, in the same format it is described in the statement.


-----Examples-----
Input
4
c=aa#bb
d12=c
res=c^d12
tmp=aa$c

Output
2
aaaa=aa#bb
res=aaaa^aaaa

Input
2
max=aaaa$bbbb
min=bbbb^aaaa

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shil is your new boss and he likes palindromes very much.  Palindrome is a string that can be read the same way in either direction, from the left to the right and from the right to the left. (ex. madam , aabaa, racecar)  

Given a string S , beautiful Palindrome is a lexicographical minimum palindrome that can be formed by rearranging all the characters of string S. In order to please your boss, find a beautiful Palindrome that can be formed with help of string S.  

String x is lexicographically less than string y, if either x is a prefix of y (and x ≠ y), or there exists such i (1 ≤ i ≤ min(|x|, |y|)), that xi < yi, and for any j (1 ≤ j < i) xj = yj. Here |a| denotes the length of the string a. The lexicographic comparison of strings is implemented by operator < in modern programming languages​​.

Input:
Only line of input contains string S. All the letters of this string will be in lower letters('a' - 'z').

Output:
Output lexicographical minimum Palindrome that can be formed by rearranging all the letters of string S. If no such Palindrome exist for given  input, print -1.

Constraints: 
1≤|S|≤100000

SAMPLE INPUT
aabcc

SAMPLE OUTPUT
acbca

Explanation

After rearranging all the characters , all the palindromes that can be formed are cabac and acbca. Out of these two lexicographical minimum one is acbca.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Finish the solution so that it takes an input `n` (integer) and returns a string that is the decimal representation of the number grouped by commas after every 3 digits.

Assume: `0 <= n < 2147483647`

## Examples

```
       1  ->           "1"
      10  ->          "10"
     100  ->         "100"
    1000  ->       "1,000"
   10000  ->      "10,000"
  100000  ->     "100,000"
 1000000  ->   "1,000,000"
35235235  ->  "35,235,235"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Cutting Figure

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've gotten an *n*<=×<=*m* sheet of squared paper. Some of its squares are painted. Let's mark the set of all painted squares as *A*. Set *A* is connected. Your task is to find the minimum number of squares that we can delete from set *A* to make it not connected.

A set of painted squares is called connected, if for every two squares *a* and *b* from this set there is a sequence of squares from the set, beginning in *a* and ending in *b*, such that in this sequence any square, except for the last one, shares a common side with the square that follows next in the sequence. An empty set and a set consisting of exactly one square are connected by definition.

Input Specification:
The first input line contains two space-separated integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=50) — the sizes of the sheet of paper. 

Each of the next *n* lines contains *m* characters — the description of the sheet of paper: the *j*-th character of the *i*-th line equals either "#", if the corresponding square is painted (belongs to set *A*), or equals "." if the corresponding square is not painted (does not belong to set *A*). It is guaranteed that the set of all painted squares *A* is connected and isn't empty.

Output Specification:
On the first line print the minimum number of squares that need to be deleted to make set *A* not connected. If it is impossible, print -1.

Demo Input:
['5 4\n####\n#..#\n#..#\n#..#\n####\n', '5 5\n#####\n#...#\n#####\n#...#\n#####\n']

Demo Output:
['2\n', '2\n']

Note:
In the first sample you can delete any two squares that do not share a side. After that the set of painted squares is not connected anymore.

The note to the second sample is shown on the figure below. To the left there is a picture of the initial set of squares. To the right there is a set with deleted squares. The deleted squares are marked with crosses.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
When Masha came to math classes today, she saw two integer sequences of length $n - 1$ on the blackboard. Let's denote the elements of the first sequence as $a_i$ ($0 \le a_i \le 3$), and the elements of the second sequence as $b_i$ ($0 \le b_i \le 3$).

Masha became interested if or not there is an integer sequence of length $n$, which elements we will denote as $t_i$ ($0 \le t_i \le 3$), so that for every $i$ ($1 \le i \le n - 1$) the following is true:   $a_i = t_i | t_{i + 1}$ (where $|$ denotes the bitwise OR operation) and  $b_i = t_i \& t_{i + 1}$ (where $\&$ denotes the bitwise AND operation). 

The question appeared to be too difficult for Masha, so now she asked you to check whether such a sequence $t_i$ of length $n$ exists. If it exists, find such a sequence. If there are multiple such sequences, find any of them.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the length of the sequence $t_i$. 

The second line contains $n - 1$ integers $a_1, a_2, \ldots, a_{n-1}$ ($0 \le a_i \le 3$) — the first sequence on the blackboard.

The third line contains $n - 1$ integers $b_1, b_2, \ldots, b_{n-1}$ ($0 \le b_i \le 3$) — the second sequence on the blackboard.


-----Output-----

In the first line print "YES" (without quotes), if there is a sequence $t_i$ that satisfies the conditions from the statements, and "NO" (without quotes), if there is no such sequence.

If there is such a sequence, on the second line print $n$ integers $t_1, t_2, \ldots, t_n$ ($0 \le t_i \le 3$) — the sequence that satisfies the statements conditions.

If there are multiple answers, print any of them.


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

Output
YES
1 3 2 0 
Input
3
1 3
3 2

Output
NO


-----Note-----

In the first example it's easy to see that the sequence from output satisfies the given conditions:   $t_1 | t_2 = (01_2) | (11_2) = (11_2) = 3 = a_1$ and $t_1 \& t_2 = (01_2) \& (11_2) = (01_2) = 1 = b_1$;  $t_2 | t_3 = (11_2) | (10_2) = (11_2) = 3 = a_2$ and $t_2 \& t_3 = (11_2) \& (10_2) = (10_2) = 2 = b_2$;  $t_3 | t_4 = (10_2) | (00_2) = (10_2) = 2 = a_3$ and $t_3 \& t_4 = (10_2) \& (00_2) = (00_2) = 0 = b_3$. 

In the second example there is no such sequence.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lucy had recently learned the game, called Natural Numbers.
The rules of the game are really simple. There are N players. At the same time, every player says one natural number. Let's call the number said by the i-th player Ai. The person with the smallest unique number (that is, the smallest number that was not said by anybody else) wins. Sometimes, there is a case when there are no unique numbers at all. Then the game is obviously a draw, so nobody wins it.
Sometimes, it's hard to determine the winner, especially, when the number of players is enormous. So in this problem, your assignment will be: given the names of the players and the numbers every of them have said. Please, tell the name of the winner, or determine that nobody wins.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of every test case consists of a single integer N - the number of players. Then, N lines will follow. Each of these N lines will consist of the player's name and the number Ai said by her, separated by a single space.

-----Output-----
For each test case, output a single line containing an answer to the corresponding test case - the name of the winner, or a string "Nobody wins.", if nobody wins the game.

-----Example-----
Input:
2
5
Kouta 1
Yuka 1
Mayu 3
Lucy 2
Nana 5
2
Lucy 2
Nana 2

Output:
Lucy
Nobody wins.

-----Scoring-----
Subtask 1 (17 points): T = 10000, 1 <= N <= 10, 1 <= Ai <= 10 

Subtask 2 (19 points): T = 10000, 1 <= N <= 10, 1 <= Ai <= 2*109

Subtask 3 (30 points): T = 100, 1 <= N <= 1000, 1<= Ai <= 2*109

Subtask 4 (34 points): T = 10, 1 <= N <= 10000, 1 <= Ai <= 2*109

You can safely assume that in all the test cases the length of any name will not exceed five letters. All the players'  names  are unique.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.