vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
-----Problem Statement-----
One of the things JEC is known for is its GR (Group Recreation) where juniors and seniors do friendly interaction ;P
As for the new session of 2020 seniors decided to have their first GR and give them some treat. Juniors were excited about it they came to college canteen aligned in a line and counted themselves one by one from left to right so that every junior gets his/her treat. But seniors played a game and they will treat only the ones who passes in this game. Game is simple all they need to do is to alternate their language (between Hindi and English) while telling their positions that is if the junior just before you told 2 in English you need to say 3 in Hindi . You do not want to be the one left without a treat. 
You are the junior standing at position $X$ from left and the counting could start from left or right you have to predict which number you have to speak and in which language when your turn comes.

-----Input:-----
- 
First line will contain $T$, number of testcases. Then the testcases follow. 
- 
Each testcase contains 2 lines first consist 2 space separated integers, $N$ (total count) , $X$ (your position from left), next line consist of 2 space separated characters  L or R (Direction from which counting starts L-left, R-Right) and H or E (the language to start counting).

-----Output:-----
For each testcase, output a single line consisting space seperated Integer P and Character L
where P is the number you will speak and L is the language (H or E).

-----Constraints-----
- $1 \leq T \leq 1000$
- $1 \leq N \leq 120$
- $1 \leq X \leq N$

-----Sample Input:-----
2
15 5
L H
20 14
R E

*try to trim extra white spaces like new line during input in case of wrong answer

-----Sample Output:-----
5 H
7 E

-----EXPLANATION:-----
- When counting starts from left with H it alternates like H E H E H….. on the fifth position H comes
- When Count starts from right with E it alternates like E H E H E H E….. with E on the position of 14th student from right.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A car moves from point A to point B at speed v meters per second. The action takes place on the X-axis. At the distance d meters from A there are traffic lights. Starting from time 0, for the first g seconds the green light is on, then for the following r seconds the red light is on, then again the green light is on for the g seconds, and so on.

The car can be instantly accelerated from 0 to v and vice versa, can instantly slow down from the v to 0. Consider that it passes the traffic lights at the green light instantly. If the car approaches the traffic lights at the moment when the red light has just turned on, it doesn't have time to pass it. But if it approaches the traffic lights at the moment when the green light has just turned on, it can move. The car leaves point A at the time 0.

What is the minimum time for the car to get from point A to point B without breaking the traffic rules?

Input

The first line contains integers l, d, v, g, r (1 ≤ l, d, v, g, r ≤ 1000, d < l) — the distance between A and B (in meters), the distance from A to the traffic lights, car's speed, the duration of green light and the duration of red light.

Output

Output a single number — the minimum time that the car needs to get from point A to point B. Your output must have relative or absolute error less than 10 - 6.

Examples

Input

2 1 3 4 5


Output

0.66666667


Input

5 4 3 1 1


Output

2.33333333

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ori and Sein have overcome many difficult challenges. They finally lit the Shrouded Lantern and found Gumon Seal, the key to the Forlorn Ruins. When they tried to open the door to the ruins... nothing happened.

Ori was very surprised, but Sein gave the explanation quickly: clever Gumon decided to make an additional defence for the door.

There are $n$ lamps with Spirit Tree's light. Sein knows the time of turning on and off for the $i$-th lamp — $l_i$ and $r_i$ respectively. To open the door you have to choose $k$ lamps in such a way that there will be a moment of time when they all will be turned on.

While Sein decides which of the $k$ lamps to pick, Ori is interested: how many ways there are to pick such $k$ lamps that the door will open? It may happen that Sein may be wrong and there are no such $k$ lamps. The answer might be large, so print it modulo $998\,244\,353$.


-----Input-----

First line contains two integers $n$ and $k$ ($1 \le n \le 3 \cdot 10^5$, $1 \le k \le n$) — total number of lamps and the number of lamps that must be turned on simultaneously.

Next $n$ lines contain two integers $l_i$ ans $r_i$ ($1 \le l_i \le r_i \le 10^9$) — period of time when $i$-th lamp is turned on.


-----Output-----

Print one integer — the answer to the task modulo $998\,244\,353$.


-----Examples-----
Input
7 3
1 7
3 8
4 5
6 7
1 3
5 10
8 9

Output
9
Input
3 1
1 1
2 2
3 3

Output
3
Input
3 2
1 1
2 2
3 3

Output
0
Input
3 3
1 3
2 3
3 3

Output
1
Input
5 2
1 3
2 4
3 5
4 6
5 7

Output
7


-----Note-----

In first test case there are nine sets of $k$ lamps: $(1, 2, 3)$, $(1, 2, 4)$, $(1, 2, 5)$, $(1, 2, 6)$, $(1, 3, 6)$, $(1, 4, 6)$, $(2, 3, 6)$, $(2, 4, 6)$, $(2, 6, 7)$.

In second test case $k=1$, so the answer is 3.

In third test case there are no such pairs of lamps.

In forth test case all lamps are turned on in a time $3$, so the answer is 1.

In fifth test case there are seven sets of $k$ lamps: $(1, 2)$, $(1, 3)$, $(2, 3)$, $(2, 4)$, $(3, 4)$, $(3, 5)$, $(4, 5)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lexicographic permutations are ordered combinations of a set of items ordered in a specific way.

For instance, the first 8 permutations of the digits 0123, in lexicographic order, are:

```
1st 0123
2nd 0132
3rd 0213
4th 0231
5th 0312
6th 0321
7th 1023
8th 1032
```

Your task is to write a function ```L( n, d )``` that will return a `string` representing the `nth` permutation of the `d` digit, starting with 0 (i.e. d=10 means all digits 0123456789).

So for `d = 4`, `L(7,4)` should return `'1023'`, and `L(4,4)` should return `'0231'`
.


Some things to bear in mind:

• The function should return a `string`, otherwise permutations beginning with a 0 will have it removed. 

• Test cases will not exceed the highest possible valid values for `n`

• The function should work for any `d` between `1` and `10`.

• A value of 1 for `n` means the 1st permutation, so `n = 0` is not a valid input.

• Oh, and no itertools ;)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string in roman no format (s)  your task is to convert it to an integer . Various symbols and their values are given below.
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
Example 1:
Input:
s = V
Output: 5
Example 2:
Input:
s = III 
Output: 3
Your Task:
Complete the function romanToDecimal() which takes a string as input parameter and returns the equivalent decimal number. 
Expected Time Complexity: O(|S|), |S| = length of string S.
Expected Auxiliary Space: O(1)
Constraints:
1<=roman no range<=3999

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call an array a_1, a_2, ..., a_m of nonnegative integer numbers good if a_1 + a_2 + ... + a_m = 2⋅(a_1 ⊕ a_2 ⊕ ... ⊕ a_m), where ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

For example, array [1, 2, 3, 6] is good, as 1 + 2 + 3 + 6 = 12 = 2⋅ 6 = 2⋅ (1⊕ 2 ⊕ 3 ⊕ 6). At the same time, array [1, 2, 1, 3] isn't good, as 1 + 2 + 1 + 3 = 7 ≠ 2⋅ 1 = 2⋅(1⊕ 2 ⊕ 1 ⊕ 3).

You are given an array of length n: a_1, a_2, ..., a_n. Append at most 3 elements to it to make it good. Appended elements don't have to be different. It can be shown that the solution always exists under the given constraints. If there are different solutions, you are allowed to output any of them. Note that you don't have to minimize the number of added elements!. So, if an array is good already you are allowed to not append elements.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10 000). The description of the test cases follows.

The first line of each test case contains a single integer n (1≤ n ≤ 10^5) — the size of the array.

The second line of each test case contains n integers a_1, a_2, ..., a_n (0≤ a_i ≤ 10^9) — the elements of the array.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

Output

For each test case, output two lines.

In the first line, output a single integer s (0≤ s≤ 3) — the number of elements you want to append.

In the second line, output s integers b_1, ..., b_s (0≤ b_i ≤ 10^{18}) — the elements you want to append to the array.

If there are different solutions, you are allowed to output any of them.

Example

Input


3
4
1 2 3 6
1
8
2
1 1


Output


0

2
4 4
3
2 6 2

Note

In the first test case of the example, the sum of all numbers is 12, and their ⊕ is 6, so the condition is already satisfied.

In the second test case of the example, after adding 4, 4, the array becomes [8, 4, 4]. The sum of numbers in it is 16, ⊕ of numbers in it is 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a bipartite graph G = (U, V, E), U is the set of vertices of the first part, V is the set of vertices of the second part and E is the set of edges. There might be multiple edges.

Let's call some subset of its edges <image> k-covering iff the graph <image> has each of its vertices incident to at least k edges. Minimal k-covering is such a k-covering that the size of the subset <image> is minimal possible.

Your task is to find minimal k-covering for each <image>, where minDegree is the minimal degree of any vertex in graph G.

Input

The first line contains three integers n1, n2 and m (1 ≤ n1, n2 ≤ 2000, 0 ≤ m ≤ 2000) — the number of vertices in the first part, the number of vertices in the second part and the number of edges, respectively.

The i-th of the next m lines contain two integers ui and vi (1 ≤ ui ≤ n1, 1 ≤ vi ≤ n2) — the description of the i-th edge, ui is the index of the vertex in the first part and vi is the index of the vertex in the second part.

Output

For each <image> print the subset of edges (minimal k-covering) in separate line.

The first integer cntk of the k-th line is the number of edges in minimal k-covering of the graph. Then cntk integers follow — original indices of the edges which belong to the minimal k-covering, these indices should be pairwise distinct. Edges are numbered 1 through m in order they are given in the input.

Examples

Input

3 3 7
1 2
2 3
1 3
3 2
3 3
2 1
2 1


Output

0 
3 3 7 4 
6 1 3 6 7 4 5 


Input

1 1 5
1 1
1 1
1 1
1 1
1 1


Output

0 
1 5 
2 4 5 
3 3 4 5 
4 2 3 4 5 
5 1 2 3 4 5 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The problem of hiding a part of a formula and searching for the hidden number is called verbal arithmetic. This time, I'm dealing with an expression in which some numbers in the expression are hidden by X. Enter the following formula and create a program that outputs the result.

Formula

* A simple one-line addition expression in the form of "number string + number string = number string".
* A "number sequence" is a sequence of numbers 0-9 and the letter X.
* It is assumed that the leftmost number in the "number string" with two or more digits is not 0.
* X must be at least one in the entire formula.



result

* The answer to the verbal arithmetic. It is one of 0 to 9 with a value of X such that the formula holds. Suppose there are no more than one answer.
* If there is no answer, the result should be “NA”.



Input

Given multiple datasets. For each dataset, an addition expression containing one or more Xs (a string of up to 126 characters without spaces) is given on one line. The number of datasets does not exceed 150.

Output

For each data set, output the result of the verbal arithmetic on one line. Print the numbers 0-9 or NA.

Example

Input

123+4X6=X79
12X+4X6=X79
XX22+89=X2XX


Output

5
NA
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Little Artem and Grasshopper

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Artem found a grasshopper. He brought it to his house and constructed a jumping area for him.

The area looks like a strip of cells 1<=×<=*n*. Each cell contains the direction for the next jump and the length of that jump. Grasshopper starts in the first cell and follows the instructions written on the cells. Grasshopper stops immediately if it jumps out of the strip. Now Artem wants to find out if this will ever happen.

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=100<=000) — length of the strip. 

Next line contains a string of length *n* which consists of characters "&lt;" and "&gt;" only, that provide the direction of the jump from the corresponding cell. Next line contains *n* integers *d**i* (1<=≤<=*d**i*<=≤<=109) — the length of the jump from the *i*-th cell.

Output Specification:
Print "INFINITE" (without quotes) if grasshopper will continue his jumps forever. Otherwise print "FINITE" (without quotes).

Demo Input:
['2\n&gt;&lt;\n1 2\n', '3\n&gt;&gt;&lt;\n2 1 1\n']

Demo Output:
['FINITE\n', 'INFINITE']

Note:
In the first sample grasshopper starts from the first cell and jumps to the right on the next cell. When he is in the second cell he needs to jump two cells left so he will jump out of the strip.

Second sample grasshopper path is 1 - 3 - 2 - 3 - 2 - 3 and so on. The path is infinite.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a string S consisting of N uppercase English letters. You are allowed to perform at most one operation of following kind: Choose any position in the string, remove the character at that position and insert it back to any other place in the string.

Find the  lexicographically smallest  string you can achieve.

-----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 each test case contains the single integer N denoting length of string S.
The second line contains the string S.

-----Output-----
For each test case, output a single line containing the answer to the corresponding test case.

-----Constraints-----
- 1 ≤ T ≤ 50
- 1 ≤ N ≤ 50
- S will consist of uppercase English letters.

-----Example-----
Input:
2
4
DCBA
7
XYZZYZZ

Output:
ADCB
XYYZZZZ

-----Explanation-----
Example case 1. The optimal solution here is to choose the last character and put it in the beginning of the string. So the answer will be ADCB
Example case 2. The optimal solution here is to choose the 5-th character (1-based index) and put it between the 2-nd and the 3-rd characters. So the answer will be XYYZZZZ

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three positive integers x, y, n. Your task is to find the nearest fraction to fraction [Image] whose denominator is no more than n. 

Formally, you should find such pair of integers a, b (1 ≤ b ≤ n; 0 ≤ a) that the value $|\frac{x}{y} - \frac{a}{b}|$ is as minimal as possible.

If there are multiple "nearest" fractions, choose the one with the minimum denominator. If there are multiple "nearest" fractions with the minimum denominator, choose the one with the minimum numerator.


-----Input-----

A single line contains three integers x, y, n (1 ≤ x, y, n ≤ 10^5).


-----Output-----

Print the required fraction in the format "a/b" (without quotes).


-----Examples-----
Input
3 7 6

Output
2/5

Input
7 2 4

Output
7/2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let’s take a prime P = 200\,003. You are given N integers A_1, A_2, \ldots, A_N. Find the sum of ((A_i \cdot A_j) \bmod P) over all N \cdot (N-1) / 2 unordered pairs of elements (i < j).

Please note that the sum isn't computed modulo P.

Constraints

* 2 \leq N \leq 200\,000
* 0 \leq A_i < P = 200\,003
* All values in input are integers.

Input

Input is given from Standard Input in the following format.


N
A_1 A_2 \cdots A_N


Output

Print one integer — the sum over ((A_i \cdot A_j) \bmod P).

Examples

Input

4
2019 0 2020 200002


Output

474287


Input

5
1 1 2 2 100000


Output

600013

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is the final leg of the most famous amazing race. The top 'n' competitors have made it to the final. The final race has just begun. The race has 'm' checkpoints. Each team can reach any of the 'm' checkpoint but after a team reaches a particular checkpoint that checkpoint gets closed and is not open to any other team. The race ends when 'k' teams finish the race. Each team travel at a constant speed throughout the race which might be different for different teams. Given the coordinates of n teams and m checkpoints and speed of individual team return the value of minimum time needed to end the race.

NOTE:

The time required for a team at coordinate (p,q) with speed 's' to reach a checkpoint at coordinate (x,y) is given by:

t = ceil( ((p-x)^2 + (q-y)^2) / s^2 ). For example if distance is 5 units and speed is 2 units then required time = ceil(25/4) = 7.

Input Format:

The first line contains 3 integers n, m and k denoting the total number of competitors, total number of checkpoints and the minimum number of teams that must complete the race in order to end the race.

This is followed by n lines each indicating the coordinates of n teams.

This is followed by m lines each indicating the coordinates of m checkpoints.

This is followed by n integers each denoting the speed of the ith team

Output Format:

Print the minimum time required to end the race.

Constraints:

1 ≤ n ≤ 200

1 ≤ m ≤ 200

1 ≤ k ≤ n

0 ≤ x coordinate of team and checkpoint ≤10^6

0 ≤ y coordinate of team and checkpoint ≤10^6

1 ≤ speed of team ≤ 50

SAMPLE INPUT
2 3 1
0 1
0 0
0 10
27 29
458 9651
5 3

SAMPLE OUTPUT
4

Explanation

For the race to finish in the minimum time the team at location (0,1) can reach the checkpoint at (0,10) .The distance between them is 9 and speed of team is 5 so required time is ceil(99))/(55))=ceil(81/25)=4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a task in Among Us in which $N$ temperature scale with unique readings are given and you have to make all of them equal. In one second you can choose an odd number and add or subtract that number in any one temperature value. Find minimum time (in seconds) required to complete the task.
$Note$: Equal value may or may not belong to array.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- First line of each testcase contains single integer $N$, the number of temperature scales
- Next line contain $A_i$ for $1 \leq i \leq N$, reading of temperature scales

-----Output:-----
For each testcase, output a single line the time (in seconds) required to complete the task.

-----Constraints-----
- $1 \leq T \leq 10^3$
- $1 \leq N \leq 10^3$
- $0 \leq A_i \leq 10^9$

-----Sample Input:-----
3

5

1 2 3 4 5

4

5 2 3 8

2

50 53  

-----Sample Output:-----
5

4

1 

-----EXPLANATION:-----
- In the $2^{nd}$ test case we need $2$ seconds to change $2$ to $8$ , $1$ second to change $3$ and $5$ to $8$ . So total time required is $2+1+1=4$ seconds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob is a dance teacher and he started dance classes recently. He observes a strange attendance pattern among his students. Initially, there are no students. On day i, a new student starts attending the class. The student stops attending the class, if and only if he has attended the class for i consecutive days. 
Also, the student resumes attending the class, if and only if he has not attended the class for i consecutive days. 

We denote the student who starts coming on day i as student i. 

To mark attendance, o denotes present and x denotes absent.  

For example, the schedule for student 1 from day 1 is as follows: 

oxoxoxoxoxoxoxoxoxox...  

The schedule for the student 3 from day 1 is as follows:  

xxoooxxxoooxxxoooxxx... 

(Student 3 starts attending the class from day 3, and stops attending from day 6, and then starts attending from day 9, and so on. )  

The schedule for the student 5 from day 1 is as follows.
xxxxoooooxxxxxoooooxxxxx...

Bob wants his students to dance in pairs. However, if the number of students coming on day i is odd, then there will be someone who can't find a partner. So Bob wants to know if the number of students coming on day i is even or odd. We denote the number of students coming on day i as N(i).  Please find out whether N(i) is even or odd.

Input format  

The first line contains an integer, T, which denotes the number of test cases. 

For each test case, there is an integer i

Output Format 

For each test case, if N(i) is even, then print even. 

If N(i) is odd, then print one line odd.

Constraints 

1 ≤ T ≤ 100 

1 ≤ i ≤ 10^{18}  

Sample Input

4
1
2
3
4

Sample Output  

odd
odd
odd
even

Explanation 

The number of students coming on day 1 is 1: only student #1 attends the class. So N(1)=1 and it is odd. 

The number of students coming on day 2 is 1:  student #2, so n(2)=1 and it is odd. 

The number of students coming on day 3 is 3: student #1, student #2, and student #3. So N(3)=3 and it is odd. 

The number of students coming on day 4 is 2: student #3 and student #4. So N(4)=2 and it is even.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
WW3 is near and Gru wants to recruit minions for his team. Gru went to the planet of minions to recruit minions, he saw that there are two villages separated by a river. He cannot recruit minions from both villages because then his team will have internal conflicts. 

Gru is now in a dilemma about which village to recruit as he wants to have the strongest possible team.

You are given coordinates of houses on the planet. Each house has exactly one minion and his power is given. The planet of minion is considered as a 2-D plane and the river is denoted by a straight line ( $y=mx+c$ ). 
$Note:$ None of the houses are situated on the river.

------ Input: ------

First-line will contain $N$, number of houses. 
Second-line will contain two integers, $m$ and $c$ denoting the river.
Next $N$ lines will have exactly 3 integers $X[i], Y[i], P[i]$ denoting the coordinates of houses and the power of minion in that house 

------ Output: ------
Print the maximum power of the team which Gru can recruit.

------ Constraints  ------
$1 ≤ N ≤ 10^{5}$
$-10^{4} ≤ m,c ≤ 10^{4}$
$-10^{4} ≤ X[i], Y[i] ≤ 10^{4}$
$ 1 ≤ P[i] ≤ 10^{4}$

----- Sample Input 1 ------ 
3
1 0
0 5 5
0 6 5
0 -8 20
----- Sample Output 1 ------ 
20

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