vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Vectors have their directions and two vectors make an angle between them. Given a set of three-dimensional vectors, your task is to find the pair among them that makes the smallest angle.



Input

The input is a sequence of datasets. A dataset specifies a set of three-dimensional vectors, some of which are directly given in the dataset and the others are generated by the procedure described below.

Each dataset is formatted as follows.


m n S W
x1 y1 z1
x2 y2 z2
:
xm ym zm


The first line contains four integers m, n, S, and W.

The integer m is the number of vectors whose three components are directly specified in the dataset. Starting from the second line, m lines have the three components of m vectors. The i-th line of which indicates the vector vi = (xi, yi, zi). All the vector components are positive integers less than or equal to 100.

The integer n is the number of vectors generated by the following procedure.


int g = S;
for(int i=m+1; i<=m+n; i++) {
x[i] = (g/7)    %100 + 1;
y[i] = (g/700)  %100 + 1;
z[i] = (g/70000)%100 + 1;
if( g%2 == 0 ) { g = (g/2); }
else           { g = (g/2) ^ W; }
}


For i = m + 1, . . . , m + n, the i-th vector vi of the set has three components x[i], y[i], and z[i] generated by this procedure.

Here, values of S and W are the parameters S and W given in the first line of the dataset. You may assume 1 ≤ S ≤ 109 and 1 ≤ W ≤ 109.

The total number of vectors satisfies 2 ≤ m + n ≤ 12 × 104. Note that exactly the same vector may be specified twice or more in a single dataset.

A line containing four zeros indicates the end of the input. The total of m+n for all the datasets in the input never exceeds 16 × 105.

Output

For each dataset, output the pair of vectors among the specified set with the smallest non-zero angle in between. It is assured that there are at least two vectors having different directions.

Vectors should be indicated by their three components. The output for a pair of vectors va and vb should be formatted in a line as follows.


xa ya za xb yb zb


Two vectors (xa, ya, za) and (xb, yb, zb) are ordered in the dictionary order, that is, va < vb if xa < xb, or if xa = xb and ya < yb, or if xa = xb, ya = yb and za < zb. When a vector pair is output, the smaller vector in this order should be output first.

If more than one pair makes the equal smallest angle, the pair that is the smallest among them in the dictionary order between vector pairs should be output. The pair (vi, vj) is smaller than the pair (vk, vl) if vi < vk, or if vi = vk and vj < vl.

Example

Input

4 0 2013 1124
1 1 1
2 2 2
2 1 1
1 2 1
2 100 131832453 129800231
42 40 46
42 40 46
0 100000 7004674 484521438
0 0 0 0


Output

1 1 1 1 2 1
42 40 46 83 79 91
92 92 79 99 99 85

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given a multi-dimensional array containing `2 or more` sub-arrays of integers. Your task is to find the maximum product that can be formed by taking any one element from each sub-array.

```
Examples:
solve( [[1, 2],[3, 4]] ) = 8. The max product is given by 2 * 4
solve( [[10,-15],[-1,-3]] ) = 45, given by (-15) * (-3)
solve( [[1,-1],[2,3],[10,-100]] ) = 300, given by (-1) * 3 * (-100)
```

More examples in test cases. Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp has a string s[1 ... n] of length n consisting of decimal digits. Polycarp performs the following operation with the string s no more than once (i.e. he can perform operation 0 or 1 time): 

  * Polycarp selects two numbers i and j (1 ≤ i ≤ j ≤ n) and removes characters from the s string at the positions i, i+1, i+2, …, j (i.e. removes substring s[i ... j]). More formally, Polycarp turns the string s into the string s_1 s_2 … s_{i-1} s_{j+1} s_{j+2} … s_{n}. 



For example, the string s = "20192020" Polycarp can turn into strings: 

  * "2020" (in this case (i, j)=(3, 6) or (i, j)=(1, 4)); 
  * "2019220" (in this case (i, j)=(6, 6)); 
  * "020" (in this case (i, j)=(1, 5)); 
  * other operations are also possible, only a few of them are listed above. 



Polycarp likes the string "2020" very much, so he is wondering if it is possible to turn the string s into a string "2020" in no more than one operation? Note that you can perform zero operations.

Input

The first line contains a positive integer t (1 ≤ t ≤ 1000 ) — number of test cases in the test. Then t test cases follow.

The first line of each test case contains an integer n (4 ≤ n ≤ 200) — length of the string s. The next line contains a string s of length n consisting of decimal digits. It is allowed that the string s starts with digit 0.

Output

For each test case, output on a separate line: 

  * "YES" if Polycarp can turn the string s into a string "2020" in no more than one operation (i.e. he can perform 0 or 1 operation); 
  * "NO" otherwise. 



You may print every letter of "YES" and "NO" in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

Example

Input


6
8
20192020
8
22019020
4
2020
5
20002
6
729040
6
200200


Output


YES
YES
YES
NO
NO
NO

Note

In the first test case, Polycarp could choose i=3 and j=6.

In the second test case, Polycarp could choose i=2 and j=5.

In the third test case, Polycarp did not perform any operations with the string.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Caisa is going to have a party and he needs to buy the ingredients for a big chocolate cake. For that he is going to the biggest supermarket in town.

Unfortunately, he has just s dollars for sugar. But that's not a reason to be sad, because there are n types of sugar in the supermarket, maybe he able to buy one. But that's not all. The supermarket has very unusual exchange politics: instead of cents the sellers give sweets to a buyer as a change. Of course, the number of given sweets always doesn't exceed 99, because each seller maximizes the number of dollars in the change (100 cents can be replaced with a dollar).

Caisa wants to buy only one type of sugar, also he wants to maximize the number of sweets in the change. What is the maximum number of sweets he can get? Note, that Caisa doesn't want to minimize the cost of the sugar, he only wants to get maximum number of sweets as change. 


-----Input-----

The first line contains two space-separated integers n, s (1 ≤ n, s ≤ 100).

The i-th of the next n lines contains two integers x_{i}, y_{i} (1 ≤ x_{i} ≤ 100; 0 ≤ y_{i} < 100), where x_{i} represents the number of dollars and y_{i} the number of cents needed in order to buy the i-th type of sugar.


-----Output-----

Print a single integer representing the maximum number of sweets he can buy, or -1 if he can't buy any type of sugar.


-----Examples-----
Input
5 10
3 90
12 0
9 70
5 50
7 0

Output
50

Input
5 5
10 10
20 20
30 30
40 40
50 50

Output
-1



-----Note-----

In the first test sample Caisa can buy the fourth type of sugar, in such a case he will take 50 sweets as a change.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A progress bar is an element of graphical interface that displays the progress of a process for this very moment before it is completed. Let's take a look at the following form of such a bar.

A bar is represented as n squares, located in line. To add clarity, let's number them with positive integers from 1 to n from the left to the right. Each square has saturation (ai for the i-th square), which is measured by an integer from 0 to k. When the bar for some i (1 ≤ i ≤ n) is displayed, squares 1, 2, ... , i - 1 has the saturation k, squares i + 1, i + 2, ... , n has the saturation 0, and the saturation of the square i can have any value from 0 to k.

So some first squares of the progress bar always have the saturation k. Some last squares always have the saturation 0. And there is no more than one square that has the saturation different from 0 and k.

The degree of the process's completion is measured in percents. Let the process be t% completed. Then the following inequation is fulfilled: 

<image>

An example of such a bar can be seen on the picture.

<image>

For the given n, k, t determine the measures of saturation for all the squares ai of the progress bar.

Input

We are given 3 space-separated integers n, k, t (1 ≤ n, k ≤ 100, 0 ≤ t ≤ 100).

Output

Print n numbers. The i-th of them should be equal to ai.

Examples

Input

10 10 54


Output

10 10 10 10 10 4 0 0 0 0 

Input

11 13 37


Output

13 13 13 13 0 0 0 0 0 0 0 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Engineers have taken over the university’s English department! As part of their plan to dominate the university, they have employed you to write their nefarious software. Their goal is to eliminate all duplicated words from all texts in the English department, because, as they say, “duplicated words are duplicated work” and “duplicated work wastes money.” Actually, what they would really say is “duplicated words are . work” and “. . wastes money”. This is what your program should do – remove all duplicate words and replace them with a period.

-----Input-----
Input is a textbook with at most $2000$ lines. Each line contains up to $100$ characters. Punctuation does not appear (it has already been removed by another programmer); words are made up of up to $20$ lower and uppercase characters (a–z). There are at most $20000$ total words in the input. Each pair of adjacent words is separated by a single space. Case does not matter when comparing words for duplicates (i.e. ‘Book’ and ‘book’ and ‘bOoK’ should be considered the same word). Input ends at end of file.

-----Output-----
Print each word the first time it appears, but thereafter if that word appears again print a period.

-----Examples-----
Sample Input:
Engineering will save the world from inefficiency
Inefficiency is a blight on the world and its
humanity
Sample Output:
Engineering will save the world from inefficiency
. is a blight on . . and its
humanity

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Like people, numbers are also friends with each other. Friendliness between any two numbers a and b is defined as the absolute difference between the two. Lower is this number more friendly the numbers are. Now you are given an array of numbers and you are required to find the friendliness of this array. This can be calculated as the sum of the friendliness of each element in the array with its closest friend in the same array. 
Example 1:
Input:
N=3
arr[] = { 4,1,5 }
Output: 5
Explanation: Sum of absolute differences is
            |4-5| + |1-4| + |5-4| = 5
Example 2:
Input:
N=3
arr[] = { 1,1,1 }
Output: 0
Explanation: Sum of absolute differences is 
             |1-1| + |1-1| + |1-1| = 0
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function sumOfMinAbsDifferences() that takes array arr and integer N as parameters and return the value of friendliness for the given array.
Expected Time Complexity: O(NLogN).
Expected Auxiliary Space: O(1).
Constraints:
2 ≤ N ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dr. Evil kidnapped Mahmoud and Ehab in the evil land because of their performance in the Evil Olympiad in Informatics (EOI). He decided to give them some problems to let them go.

Dr. Evil is interested in sets, He has a set of n integers. Dr. Evil calls a set of integers evil if the MEX of it is exactly x. the MEX of a set of integers is the minimum non-negative integer that doesn't exist in it. For example, the MEX of the set {0, 2, 4} is 1 and the MEX of the set {1, 2, 3} is 0 .

Dr. Evil is going to make his set evil. To do this he can perform some operations. During each operation he can add some non-negative integer to his set or erase some element from it. What is the minimal number of operations Dr. Evil has to perform to make his set evil?


-----Input-----

The first line contains two integers n and x (1 ≤ n ≤ 100, 0 ≤ x ≤ 100) — the size of the set Dr. Evil owns, and the desired MEX.

The second line contains n distinct non-negative integers not exceeding 100 that represent the set.


-----Output-----

The only line should contain one integer — the minimal number of operations Dr. Evil should perform.


-----Examples-----
Input
5 3
0 4 5 6 7

Output
2

Input
1 0
0

Output
1

Input
5 0
1 2 3 4 5

Output
0



-----Note-----

For the first test case Dr. Evil should add 1 and 2 to the set performing 2 operations.

For the second test case Dr. Evil should erase 0 from the set. After that, the set becomes empty, so the MEX of it is 0.

In the third test case the set is already evil.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Many airports have moving conveyor belts in the corridors between halls and terminals. Instead of walking on the floor, passengers can choose to stand on a conveyor or, even better, walk on a conveyor to get to the end of the corridor much faster.

The brand new Delft City Airport uses a similar system. However, in line with the latest fashion in airport architecture, there are no corridors: the entire airport is one big hall with a bunch of conveyor lines laid out on the floor arbitrarily.

To get from a certain point $A$ to a certain point $B$, a passenger can use any combination of walking on the floor and walking on conveyors. Passengers can hop on or off a conveyor at any point along the conveyor. It is also possible to cross a conveyor without actually standing on it.

Walking on the floor goes at a speed of $1$ meter/second.

 Walking forward on a conveyor goes at a total speed of $2$ meter/second.

 Walking in reverse direction on a conveyor is useless and illegal, but you may walk on the floor immediately next to the conveyor. (Conveyors are infinitely thin.)

How fast can you get from $A$ to $B$?

-----Input-----
The first line contains four floating point numbers, $X_ A$, $Y_ A$, $X_ B$, and $Y_ B$. They describe the coordinates of your initial location $A = (X_ A,Y_ A)$ and your final location $B = (X_ B,Y_ B)$.

The second line contains an integer $N$, the number of conveyors in the hall ($0 \leq N \leq 100$). The following $N$ lines each contain four floating point numbers, $X_1$, $Y_1$, $X_2$, and $Y_2$, describing a conveyor which starts at the point $(X_1,Y_1)$ and ends at the point $(X_2,Y_2)$, running in a straight line from start to end.

All coordinates are floating point numbers in the range ($0 \leq X, Y \leq 1000.0$), expressed in units of meters, given with at most $6$ decimals after the decimal point.

Conveyors are at least $1$ meter long. Conveyors do not intersect or touch. Your start and destination are not on any conveyor.

-----Output-----
Write one line with a floating point number, the minimum time (in seconds) needed to get from $A$ to $B$ in seconds.

Your answer may have an absolute error of at most $10^{-4}$.

-----Examples-----
Sample Input 1:
60.0 0.0 50.0 170.0
3
40.0 0.0 0.0 0.0
5.0 20.0 5.0 170.0
95.0 0.0 95.0 80.0
Sample Output 1:
168.7916512460

Sample Input 2:
60.0 0.0 50.0 170.0
3
40.0 0.0 0.0 0.0
5.0 20.0 5.0 170.0
95.0 0.0 95.0 100.0
Sample Output 2:
163.5274740179

Sample Input 3:
0.0 1.0 4.0 1.0
1
0.0 0.0 4.0 0.0
Sample Output 3:
3.7320508076

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

Time Limit: 5 seconds

Memory Limit: 64 megabytes

Problem Description:
A new e-mail service "Berlandesk" is going to be opened in Berland in the near future. The site administration wants to launch their project as soon as possible, that's why they ask you to help. You're suggested to implement the prototype of site registration system. The system should work on the following principle. 

Each time a new user wants to register, he sends to the system a request with his name. If such a name does not exist in the system database, it is inserted into the database, and the user gets the response OK, confirming the successful registration. If the name already exists in the system database, the system makes up a new user name, sends it to the user as a prompt and also inserts the prompt into the database. The new name is formed by the following rule. Numbers, starting with 1, are appended one after another to name (name1, name2, ...), among these numbers the least *i* is found so that name*i* does not yet exist in the database.

Input Specification:
The first line contains number *n* (1<=≤<=*n*<=≤<=105). The following *n* lines contain the requests to the system. Each request is a non-empty line, and consists of not more than 32 characters, which are all lowercase Latin letters.

Output Specification:
Print *n* lines, which are system responses to the requests: OK in case of successful registration, or a prompt with a new name, if the requested name is already taken.

Demo Input:
['4\nabacaba\nacaba\nabacaba\nacab\n', '6\nfirst\nfirst\nsecond\nsecond\nthird\nthird\n']

Demo Output:
['OK\nOK\nabacaba1\nOK\n', 'OK\nfirst1\nOK\nsecond1\nOK\nthird1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Probably everyone has experienced an awkward situation due to shared armrests between seats in cinemas. A highly accomplished cinema manager named "Chef" decided to solve this problem.

When a customer wants to buy a ticket, the clerk at the ticket window asks the visitor if they need the armrests, and if so, which of them: left, right, or both. We know that out of the audience expected to show up, L of them only need the left armrest, R of them need just the right one, Z need none and B need both. Your task is to calculate the maximum number of people that can attend the show. In the cinema hall there are N rows with M seats each. There is only one armrest between two adjacent seats. Seats at the beginning and at the end of the row have two armrests

-----Input-----

Input begins with an integer T: the number of test cases.

Each test case consists of a single line with 6 space-separated integers: N, M, Z, L, R, B.

-----Output-----

For each test case, output a line containing the answer for the task.

-----Constraints and Subtasks-----
- 1 ≤ T ≤ 105 
Subtask 1 : 10 points 
- 1 ≤ N, M ≤ 3 
- 0 ≤ Z, L, R, B ≤ 3 
Subtask 2 : 20 points 
- 1 ≤ N, M ≤ 30 
- 0 ≤ Z, L, R ≤ 30 
- 0 ≤ B ≤ 109 
Subtask 3 : 30 points
- 1 ≤ N, M ≤ 106 
- 0 ≤ Z, L, R ≤ 106 
- 0 ≤ B ≤ 1016 
Subtask 4 : 40 points
- 1 ≤ N, M ≤ 108 
- 0 ≤ Z, L, R, B ≤ 1016 

-----Example-----
Input:2
2 2 3 2 1 1
3 3 1 2 0 9

Output:4
8

-----Explanation-----
'L' - needs left

'R - needs right

'Z' - doesn't need any

'B' - needs both

'-' - empty place

Example case 1.
ZZ

ZB
Example case 2.
LLB

BZB

B-B

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

Chieno and Cacao are sisters who work in the same coffee shop. The two are very close, and one day they decided to play a table game.

The game uses the board of R square x C square and the rabbit TP as a piece. Each square on the board is painted white or black. First, place the TP in the lower right corner (R, C) of the board, and the two perform the following actions alternately. Assuming that the current position of TP is (a, b), one jumpable position (i, j) is selected from there, and TP is made to jump there. The positions (i, j) where TP can jump satisfy all of the following.

1. 1 ≤ i ≤ R and 1 ≤ j ≤ C and i ≤ a and j ≤ b and 1 ≤ (a-i) + (b-j) ≤ K
2. (i, j) is a white square



If you can no longer jump TP on your turn, you lose.

Chieno is on the play and Cacao is on the play. Cacao can look ahead to the end of the game in his head and always behaves optimally. At this time, determine if there is a way for Chieno to win.

Constraints

* 1 ≤ R, C ≤ 1000
* 1 ≤ K ≤ 2000
* GR and C are “.”

Input

The input is given in the following format.


R C K
G1,1 G1,2 ... G1,C
G2,1 G2,2 ... G2, C
::
GR, 1 GR, 2 ... GR, C


The first line is given three integers R, C, K separated by blanks. C "." Or "#" are given as board information in the next R line. Gi, j represents the color of the board position (i, j), "." Represents white, and "#" represents black.

Output

Print "Chieno" if there is a way for Chieno to win, or "Cacao" if it doesn't.

Examples

Input

3 3 2
...
...
...


Output

Chieno


Input

3 3 2
.#
.#.
..


Output

Cacao

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gitam is a priest in his village. He needs to pay his respects to k shrines which his all ancestors have visited and had asked their successors to pay the respect. But he hates walking so he wants to minimize the distance he has to travel to pay his respects. As he is busy packing he asks you to help him. He has acquired a bunch of portal scrolls through which he can create portal networks. gateways can only be created at shrines , and after entering a portal a he can exit at any desired portal. You have to give the minimum distance Gitam has to travel. There are number of cities which don’t have shrines but that can be traveled through.
You will be given n the number of cities and out of which first k cities have shrines. There is road connecting two cities which will be defined by three integers a, b and c where a and b are the cities and c is the distance between the cities. You have to calculate the minimum distance that need to be walked for this pilgrimage given that there is no restriction on number of gateways that can be created but need to be created at shrines. After you have told him the distance he’ll decide whether it’s worth undertaking or not. You can assume that he starts from 1st city.

[Input]
First line contains integer t denoting number of test cases.
First line of every test case consists of 3 integers n, m and k denoting number of cities, number of roads and number of shrines respectively.
Next m lines of test case consists of 3 space separated integers a, b and c, where a and b are cities and c is the distance between them.

[Output]
For each test case print a single integer containing the minimum distance he need to walk for the pilgrimage.

[Constraints]
1 ≤ t ≤ 20
1 ≤ n ≤ 100
n-1 ≤ m ≤ (n*(n-1))/2
1 ≤ k ≤ n
1 ≤ a,b ≤ n
1 ≤ c ≤ 1000000

SAMPLE INPUT
1
5 10 3
1 2 10
1 3 5
1 4 10
1 5 80
2 3 9
2 4 1
2 5 20
3 4 100
3 5 2
4 5 20

SAMPLE OUTPUT
14

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