vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Pia is getting ready for her flight to the NWERC 2018 in Eindhoven. As she is packing her hard drive, she remembers the airline’s ridiculous weight restrictions, which may pose a problem. You see, the hard drive is essentially a string of ones and zeros, and its weight depends on the number of “bit changes” in it: for any two adjacent bits storing two different values, the hard drive gets slightly heavier, so Pia cannot just store arbitrary information on it.

To make matters worse, the drive is so old that some bits are already broken and will always store zeros. The first bit will never be broken, but the last bit will always be.

Pia decides to treat this situation as a challenge: she is now trying to modify the information on the hard drive so that it has exactly the maximum number of bit changes permitted by the airline. However, the broken bits make this harder than expected, so she needs your help.

Find a bit pattern which can be stored on the hard drive and has exactly the desired number of bit changes.

-----Input-----
The input consists of:
 - One line with three integers $n$, $c$, and $b$ ($2 \leq n \leq 5\cdot 10^5$, $1 \leq c, b \le n-1$), the size of the hard drive in bits, the desired amount of bit changes, and the number of broken bits. The positions on the hard drive are numbered from $1$ to $n$.
 - One line with $b$ integers $z_1, \ldots , z_ b$ ($2 \leq z_1 < z_2 < \ldots < z_ b = n$), the positions of the broken bits on the hard drive.

-----Output-----
Output a bit string of length $n$, representing Pia’s hard drive and containing exactly $c$ bit changes. If there are multiple valid solutions, you may output any one of them. It is guaranteed that at least one solution exists.

-----Examples-----
Sample Input:
5 2 3
2 3 5
Sample Output:
00010

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Once when Gerald studied in the first year at school, his teacher gave the class the following homework. She offered the students a string consisting of *n* small Latin letters; the task was to learn the way the letters that the string contains are written. However, as Gerald is too lazy, he has no desire whatsoever to learn those letters. That's why he decided to lose some part of the string (not necessarily a connected part). The lost part can consist of any number of segments of any length, at any distance from each other. However, Gerald knows that if he loses more than *k* characters, it will be very suspicious. 

Find the least number of distinct characters that can remain in the string after no more than *k* characters are deleted. You also have to find any possible way to delete the characters.

Input Specification:
The first input data line contains a string whose length is equal to *n* (1<=≤<=*n*<=≤<=105). The string consists of lowercase Latin letters. The second line contains the number *k* (0<=≤<=*k*<=≤<=105).

Output Specification:
Print on the first line the only number *m* — the least possible number of different characters that could remain in the given string after it loses no more than *k* characters.

Print on the second line the string that Gerald can get after some characters are lost. The string should have exactly *m* distinct characters. The final string should be the subsequence of the initial string. If Gerald can get several different strings with exactly *m* distinct characters, print any of them.

Demo Input:
['aaaaa\n4\n', 'abacaba\n4\n', 'abcdefgh\n10\n']

Demo Output:
['1\naaaaa\n', '1\naaaa\n', '0\n\n']

Note:
In the first sample the string consists of five identical letters but you are only allowed to delete 4 of them so that there was at least one letter left. Thus, the right answer is 1 and any string consisting of characters "a" from 1 to 5 in length.

In the second sample you are allowed to delete 4 characters. You cannot delete all the characters, because the string has length equal to 7. However, you can delete all characters apart from "a" (as they are no more than four), which will result in the "aaaa" string.

In the third sample you are given a line whose length is equal to 8, and *k* = 10, so that the whole line can be deleted. The correct answer is 0 and an empty string.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In vardhaman college of engineering, there is competition with name treasure lock.
To make this competition the key for the lock should satisfy following rules.
1 .3, 5, or both as its digits. No other digit is allowed.
2. Number of times 3 appears is divisible by 5.
3. Number of times 5 appears is divisible by 3.

Rakesh is very eager to win the championship. He is developing a code for that key.Assume yourself in that situation and solve for the key.

INPUT:
first line contains T testcases.
Next T lines consists of the number.
OUTPUT:
Output the number satisfying the above conditions.
if n cannot satisfy the above conditions print -1.

0<t<10
0<n<1000

SAMPLE INPUT
4
1
3
5
17

SAMPLE OUTPUT
-1
555
33333
55555555555533333

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program which reads two integers a and b, and calculates the following values:

* a ÷ b: d (in integer)
* remainder of a ÷ b: r (in integer)
* a ÷ b: f (in real number)

Constraints

* 1 ≤ a, b ≤ 109

Input

Two integers a and b are given in a line.

Output

Print d, r and f separated by a space in a line. For f, the output should not contain an absolute error greater than 10-5.

Example

Input

3 2


Output

1 1 1.50000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sophia has discovered several alien languages. Suprisingly, all of these languages have an alphabet, and each of them may contain thousands of characters! Also, all the words in a language have the same number of characters in it.

However, the aliens like their words to be aesthetically pleasing, which for them means that for the $i^{th}$ letter of an $n$-letter alphabet (letters are indexed $1\ldots n$):

if $2i>n$, then the $i^{th}$ letter may be the last letter of a word, or it may be immediately followed by any letter, including itself.

if $2i\leq n$, then the $i^{th}$ letter can not be the last letter of a word and also can only be immediately followed by $j^{th}$ letter if and only if $j\geq2i$.  

Sophia wants to know how many different words exist in this language. Since the result may be large, she wants to know this number, modulo $100000007(10^8+7)$.

Input Format

The first line contains $\boldsymbol{\boldsymbol{t}}$, the number of test cases. The first line is followed by $\boldsymbol{\boldsymbol{t}}$ lines, each line denoting a test case. Each test case will have two space-separated integers $n$, $m$ which denote the number of letters in the language and the length of words in this language respectively.

Constraints

$1\leq t\leq5$  
$1\leq n\leq10^5$  
$1\leq m\leq5\cdot10^5$  

Output Format

For each test case, output the number of possible words modulo $100000007(10^8+7)$.

Sample Input
3
1 3
2 3
3 2

Sample Output
1
3
6

Explanation

For the first test case, there's one letter ('a') and all the words consist of $3$ letters. There's only one possibility which is "aaa".  

For the second test case, there are two letters ('a' and 'b') and all the words are of $3$ letters. The possible strings are "abb", "bab", & "bbb". The words can end only with 'b' because $2\cdot\text{index}(b)=2\cdot2>2$ and for 'a', it's $2\cdot\text{index}(a)=2\cdot1\leq2$. "aab" is not allowed because 'a' can not be followed immediately by 'a'. For a word of length 4 and alphabet of size 2, "abab" would be allowed.

For the third test case, there are three letters ('a', 'b' and 'c') and all of the words are $2$ letters. The words can only end with 'b' or 'c'. The possible words are "ab", "ac", "bb", "cc", "bc", "cb".

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A tennis tournament with *n* participants is running. The participants are playing by an olympic system, so the winners move on and the losers drop out.

The tournament takes place in the following way (below, *m* is the number of the participants of the current round):
 -  let *k* be the maximal power of the number 2 such that *k*<=≤<=*m*, -  *k* participants compete in the current round and a half of them passes to the next round, the other *m*<=-<=*k* participants pass to the next round directly, -  when only one participant remains, the tournament finishes. 
Each match requires *b* bottles of water for each participant and one bottle for the judge. Besides *p* towels are given to each participant for the whole tournament.

Find the number of bottles and towels needed for the tournament.

Note that it's a tennis tournament so in each match two participants compete (one of them will win and the other will lose).

Input Specification:
The only line contains three integers *n*,<=*b*,<=*p* (1<=≤<=*n*,<=*b*,<=*p*<=≤<=500) — the number of participants and the parameters described in the problem statement.

Output Specification:
Print two integers *x* and *y* — the number of bottles and towels need for the tournament.

Demo Input:
['5 2 3\n', '8 2 4\n']

Demo Output:
['20 15\n', '35 32\n']

Note:
In the first example will be three rounds:
 1.  in the first round will be two matches and for each match 5 bottles of water are needed (two for each of the participants and one for the judge), 1.  in the second round will be only one match, so we need another 5 bottles of water, 1.  in the third round will also be only one match, so we need another 5 bottles of water. 
So in total we need 20 bottles of water.

In the second example no participant will move on to some round directly.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three positive (i.e. strictly greater than zero) integers x, y and z.

Your task is to find positive integers a, b and c such that x = max(a, b), y = max(a, c) and z = max(b, c), or determine that it is impossible to find such a, b and c.

You have to answer t independent test cases. Print required a, b and c in any (arbitrary) order.

Input

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

The only line of the test case contains three integers x, y, and z (1 ≤ x, y, z ≤ 10^9).

Output

For each test case, print the answer:

  * "NO" in the only line of the output if a solution doesn't exist; 
  * or "YES" in the first line and any valid triple of positive integers a, b and c (1 ≤ a, b, c ≤ 10^9) in the second line. You can print a, b and c in any order. 

Example

Input


5
3 2 3
100 100 100
50 49 49
10 30 20
1 1000000000 1000000000


Output


YES
3 2 1
YES
100 100 100
NO
NO
YES
1 1 1000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is given two integers A and C such that A ≤ C. 

Chef wants to find whether there exists any integer B such that A, B, and C are in [arithmetic progression].

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two space-separated integers A and C, the given integers.

------ Output Format ------ 

For each test case, output -1 if there exists no integer B such that A, B, and C are in arithmetic progression. Else, output the value of B.

------ Constraints ------ 

$1 ≤ T ≤ 60$
$1 ≤ A ≤ C ≤ 10$

----- Sample Input 1 ------ 
4
3 5
6 6
2 7
1 9

----- Sample Output 1 ------ 
4
6
-1
5

----- explanation 1 ------ 
Test case $1$: Considering $B = 4$, the three integers are in arithmetic progression as $B-A = C-B = 1$.

Test case $2$: Considering $B = 6$, the three integers are in arithmetic progression as $B-A = C-B = 0$.

Test case $3$: There exists no integral value of $B$ such that $A, B, $ and $C$ are in arithmetic progression.

Test case $4$: Considering $B = 5$, the three integers are in arithmetic progression as $B-A = C-B = 4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Three Parts of the Array

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an array $d_1, d_2, \dots, d_n$ consisting of $n$ integer numbers.

Your task is to split this array into three parts (some of which may be empty) in such a way that each element of the array belongs to exactly one of the three parts, and each of the parts forms a consecutive contiguous subsegment (possibly, empty) of the original array. 

Let the sum of elements of the first part be $sum_1$, the sum of elements of the second part be $sum_2$ and the sum of elements of the third part be $sum_3$. Among all possible ways to split the array you have to choose a way such that $sum_1 = sum_3$ and $sum_1$ is maximum possible.

More formally, if the first part of the array contains $a$ elements, the second part of the array contains $b$ elements and the third part contains $c$ elements, then:

$$sum_1 = \sum\limits_{1 \le i \le a}d_i,$$ $$sum_2 = \sum\limits_{a + 1 \le i \le a + b}d_i,$$ $$sum_3 = \sum\limits_{a + b + 1 \le i \le a + b + c}d_i.$$

The sum of an empty array is $0$.

Your task is to find a way to split the array such that $sum_1 = sum_3$ and $sum_1$ is maximum possible.

Input Specification:
The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in the array $d$.

The second line of the input contains $n$ integers $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$) — the elements of the array $d$.

Output Specification:
Print a single integer — the maximum possible value of $sum_1$, considering that the condition $sum_1 = sum_3$ must be met.

Obviously, at least one valid way to split the array exists (use $a=c=0$ and $b=n$).

Demo Input:
['5\n1 3 1 1 4\n', '5\n1 3 2 1 4\n', '3\n4 1 2\n']

Demo Output:
['5\n', '4\n', '0\n']

Note:
In the first example there is only one possible splitting which maximizes $sum_1$: $[1, 3, 1], [~], [1, 4]$.

In the second example the only way to have $sum_1=4$ is: $[1, 3], [2, 1], [4]$.

In the third example there is only one way to split the array: $[~], [4, 1, 2], [~]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Gregorian calendar a typical year consists of 365 days and 12 months. The numbers of days in the months are: 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31. If year index is divisible by 400, or divisible by 4 but not by 100, the year becomes leap year, with one extra day in the second month (the one which typically has 28 days).

You are given the index of the year and the index of the day in the year. Find out the date of this day (day and month it will fall upon).

Input

The first line of input contains the year index, between 1600 and 2400, inclusive. The second line contains the day index, between 1 and 366, inclusive. It is guaranteed that the day index will be valid for this year, i.e., day 366 will occur only in a leap year.

Output

Output the index of the day and the index of the month, separated with a space.

Examples

Input

2011
324


Output

20 11


Input

2012
274


Output

30 9

Note

All indexes are 1-based.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An infinitely long railway has a train consisting of n cars, numbered from 1 to n (the numbers of all the cars are distinct) and positioned in arbitrary order. David Blaine wants to sort the railway cars in the order of increasing numbers. In one move he can make one of the cars disappear from its place and teleport it either to the beginning of the train, or to the end of the train, at his desire. What is the minimum number of actions David Blaine needs to perform in order to sort the train?


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 100 000) — the number of cars in the train. 

The second line contains n integers p_{i} (1 ≤ p_{i} ≤ n, p_{i} ≠ p_{j} if i ≠ j) — the sequence of the numbers of the cars in the train.


-----Output-----

Print a single integer — the minimum number of actions needed to sort the railway cars.


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

Output
2

Input
4
4 1 3 2

Output
2



-----Note-----

In the first sample you need first to teleport the 4-th car, and then the 5-th car to the end of the train.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Mister B and Book Reading

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mister B once received a gift: it was a book about aliens, which he started read immediately. This book had *c* pages.

At first day Mister B read *v*0 pages, but after that he started to speed up. Every day, starting from the second, he read *a* pages more than on the previous day (at first day he read *v*0 pages, at second — *v*0<=+<=*a* pages, at third — *v*0<=+<=2*a* pages, and so on). But Mister B is just a human, so he physically wasn't able to read more than *v*1 pages per day.

Also, to refresh his memory, every day, starting from the second, Mister B had to reread last *l* pages he read on the previous day. Mister B finished the book when he read the last page for the first time.

Help Mister B to calculate how many days he needed to finish the book.

Input Specification:
First and only line contains five space-separated integers: *c*, *v*0, *v*1, *a* and *l* (1<=≤<=*c*<=≤<=1000, 0<=≤<=*l*<=&lt;<=*v*0<=≤<=*v*1<=≤<=1000, 0<=≤<=*a*<=≤<=1000) — the length of the book in pages, the initial reading speed, the maximum reading speed, the acceleration in reading speed and the number of pages for rereading.

Output Specification:
Print one integer — the number of days Mister B needed to finish the book.

Demo Input:
['5 5 10 5 4\n', '12 4 12 4 1\n', '15 1 100 0 0\n']

Demo Output:
['1\n', '3\n', '15\n']

Note:
In the first sample test the book contains 5 pages, so Mister B read it right at the first day.

In the second sample test at first day Mister B read pages number 1 - 4, at second day — 4 - 11, at third day — 11 - 12 and finished the book.

In third sample test every day Mister B read 1 page of the book, so he finished in 15 days.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Поликарп мечтает стать программистом и фанатеет от степеней двойки. Среди двух чисел ему больше нравится то, которое делится на большую степень числа 2. 

По заданной последовательности целых положительных чисел a_1, a_2, ..., a_{n} требуется найти r — максимальную степень числа 2, на которую делится хотя бы одно из чисел последовательности. Кроме того, требуется вывести количество чисел a_{i}, которые делятся на r.


-----Входные данные-----

В первой строке записано целое число n (1 ≤ n ≤ 100) — длина последовательности a.

Во второй строке записана последовательность целых чисел a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Выходные данные-----

Выведите два числа:

  r — максимальную степень двойки, на которую делится хотя бы одно из чисел заданной последовательности,  количество элементов последовательности, которые делятся на r. 


-----Примеры-----
Входные данные
5
80 7 16 4 48

Выходные данные
16 3

Входные данные
4
21 5 3 33

Выходные данные
1 4



-----Примечание-----

В первом тестовом примере максимальная степень двойки, на которую делится хотя бы одно число, равна 16 = 2^4, на неё делятся числа 80, 16 и 48.

Во втором тестовом примере все четыре числа нечётные, поэтому делятся только на 1 = 2^0. Это и будет максимальной степенью двойки для данного примера.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are three arrays a, b and c. Each of them consists of n integers. SmallY wants to find three integers u, v, w (0 ≤ u, v, w ≤ n) such that the following condition holds: each number that appears in the union of a, b and c, appears either in the first u elements of a, or in the first v elements of b, or in the first w elements of c. Of course, SmallY doesn't want to have huge numbers u, v and w, so she wants sum u + v + w to be as small as possible.

Please, help her to find the minimal possible sum of u + v + w.

Input

The first line contains a single integer n (1 ≤ n ≤ 105). The second line contains n space-separated integers a1, a2, ..., an — array a. The third line contains the description of array b in the same format. The fourth line contains the description of array c in the same format. The following constraint holds: 1 ≤ ai, bi, ci ≤ 109.

Output

Print a single integer — the minimum possible sum of u + v + w.

Examples

Input

3
1 1 101
1 2 1
3 2 1


Output

5

Input

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


Output

5

Note

In the first example you should choose u = 3, v = 0, w = 2. 

In the second example you should choose u = 1, v = 3, w = 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
User ainta is making a web site. This time he is going to make a navigation of the pages. In his site, there are n pages numbered by integers from 1 to n. Assume that somebody is on the p-th page now. The navigation will look like this:

<< p - k p - k + 1 ... p - 1 (p) p + 1 ... p + k - 1 p + k >>

When someone clicks the button "<<" he is redirected to page 1, and when someone clicks the button ">>" he is redirected to page n. Of course if someone clicks on a number, he is redirected to the corresponding page.

There are some conditions in the navigation:

  * If page 1 is in the navigation, the button "<<" must not be printed. 
  * If page n is in the navigation, the button ">>" must not be printed. 
  * If the page number is smaller than 1 or greater than n, it must not be printed. 



You can see some examples of the navigations. Make a program that prints the navigation.

Input

The first and the only line contains three integers n, p, k (3 ≤ n ≤ 100; 1 ≤ p ≤ n; 1 ≤ k ≤ n)

Output

Print the proper navigation. Follow the format of the output from the test samples.

Examples

Input

17 5 2


Output

&lt;&lt; 3 4 (5) 6 7 &gt;&gt; 

Input

6 5 2


Output

&lt;&lt; 3 4 (5) 6 

Input

6 1 2


Output

(1) 2 3 &gt;&gt; 

Input

6 2 2


Output

1 (2) 3 4 &gt;&gt;

Input

9 6 3


Output

&lt;&lt; 3 4 5 (6) 7 8 9

Input

10 6 3


Output

&lt;&lt; 3 4 5 (6) 7 8 9 &gt;&gt;

Input

8 5 4


Output

1 2 3 4 (5) 6 7 8 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A company has N members, who are assigned ID numbers 1, ..., N.
Every member, except the member numbered 1, has exactly one immediate boss with a smaller ID number.
When a person X is the immediate boss of a person Y, the person Y is said to be an immediate subordinate of the person X.
You are given the information that the immediate boss of the member numbered i is the member numbered A_i. For each member, find how many immediate subordinates it has.

-----Constraints-----
 - 2 \leq N \leq 2 \times 10^5
 - 1 \leq A_i < i

-----Input-----
Input is given from Standard Input in the following format:
N
A_2 ... A_N

-----Output-----
For each of the members numbered 1, 2, ..., N, print the number of immediate subordinates it has, in its own line.

-----Sample Input-----
5
1 1 2 2

-----Sample Output-----
2
2
0
0
0

The member numbered 1 has two immediate subordinates: the members numbered 2 and 3.
The member numbered 2 has two immediate subordinates: the members numbered 4 and 5.
The members numbered 3, 4, and 5 do not have immediate subordinates.

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