vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
This is an interactive problem.

Ayush devised yet another scheme to set the password of his lock. The lock has n slots where each slot can hold any non-negative integer. The password P is a sequence of n integers, i-th element of which goes into the i-th slot of the lock.

To set the password, Ayush comes up with an array A of n integers each in the range [0, 2^{63}-1]. He then sets the i-th element of P as the [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR) of all integers in the array except A_i.

You need to guess the password. To make a query, you can choose a non-empty subset of indices of the array and ask the bitwise OR all elements of the array with index in this subset. You can ask no more than 13 queries.

Input

The first line of input contains one integer n (2 ≤ n ≤ 1000) — the number of slots in the lock.

Interaction

To ask a query print a single line: 

  * In the beginning print "? c " (without quotes) where c (1 ≤ c ≤ n) denotes the size of the subset of indices being queried, followed by c distinct space-separated integers in the range [1, n]. 



For each query, you will receive an integer x — the bitwise OR of values in the array among all the indices queried. If the subset of indices queried is invalid or you exceeded the number of queries then you will get x = -1. In this case, you should terminate the program immediately.

When you have guessed the password, print a single line "! " (without quotes), followed by n space-separated integers — the password sequence.

Guessing the password does not count towards the number of queries asked.

The interactor is not adaptive. The array A does not change with queries.

After printing a query do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see the documentation for other languages.



Hacks

To hack the solution, use the following test format:

On the first line print a single integer n (2 ≤ n ≤ 1000) — the number of slots in the lock. The next line should contain n space-separated integers in the range [0, 2^{63} - 1] — the array A.

Example

Input


3

1

2

4



Output


? 1 1

? 1 2

? 1 3

! 6 5 3

Note

The array A in the example is \{{1, 2, 4\}}. The first element of the password is bitwise OR of A_2 and A_3, the second element is bitwise OR of A_1 and A_3 and the third element is bitwise OR of A_1 and A_2. Hence the password sequence is \{{6, 5, 3\}}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
## Enough is enough!

Alice and Bob were on a holiday. Both of them took many pictures of the places they've been, and now they want to show Charlie their entire collection. However, Charlie doesn't like these sessions, since the motive usually repeats. He isn't fond of seeing the Eiffel tower 40 times. He tells them that he will only sit during the session if they show the same motive at most N times. Luckily, Alice and Bob are able to encode the motive as a number. Can you help them to remove numbers such that their list contains each number only up to N times, without changing the order?

## Task

Given a list lst and a number N, create a new list that contains each number of lst at most N times without reordering. For example if N = 2, and the input is [1,2,3,1,2,1,2,3], you take [1,2,3,1,2], drop the next [1,2] since this would lead to 1 and 2 being in the result 3 times, and then take 3, which leads to [1,2,3,1,2,3].

~~~if:nasm
## NASM notes

Write the output numbers into the `out` parameter, and return its length.

The input array will contain only integers between 1 and 50 inclusive. Use it to your advantage.
~~~

~~~if:c
For C:
* Assign the return array length to the pointer parameter `*szout`.
* Do not mutate the input array.
~~~

## Example
```python
  delete_nth ([1,1,1,1],2) # return [1,1]
  
  delete_nth ([20,37,20,21],1) # return [20,37,21]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The number 81 has a special property, a certain power of the sum of its digits is equal to 81 (nine squared). Eighty one (81), is the first number in having this property (not considering numbers of one digit). 
The next one, is 512.
Let's see both cases with the details

8 + 1 = 9 and 9^(2) = 81

512 = 5 + 1 + 2 = 8 and 8^(3) = 512

We need to make a function, ```power_sumDigTerm()```, that receives a number ```n``` and may output the ```n-th term``` of this sequence of numbers.
The cases we presented above means that

power_sumDigTerm(1) == 81

power_sumDigTerm(2) == 512


Happy coding!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of integers. Check whether there exists a number in this array which is divisible by all other numbers in this array. Output 1, if such a number exists, and 0 otherwise.

Input

The only line of the input contains a list of space-separated integers ai (1 ≤ ai ≤ 100) — elements of the array. The size of the array is between 2 and 10, inclusive. Note that the size of the array is not given explicitly!

Output

Output 1 if there exists element of this array which is divisible by all other elements of the array, and 0 otherwise.

Examples

Input

6 12 4


Output

1


Input

3 13


Output

0


Input

26 13 12


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Emil loves his electric moped. He loves it so much that he rides it through rain, snow, wind and ice. Some day, he will be able to fly with it. This weekend, Emil is on a vacation in New York. He has compiled a list of cool places to visit, as well as a list of all one-way streets between these places, and now it is time for some sightseeing! 

One sightseeing trip consists of $S$ places and exactly $S$ streets which connect them. He starts by travelling to one of these places by subway, with his moped on his back. Then he starts riding his moped to each place of the trip in turn, finally returning to where he started in the current trip. Then he goes back to the subway, with his moped on his back, and goes for the next trip. He does this until he has enjoyed all of the trips.

Since it’s very hard to determine if Emil can visit all of the places he wants to see in a single trip of this kind, he has instead asked you to help him split all of the $N$ places in town into a number of trips, such that each place in town is included in exactly one trip.

Given all the places Emil wants to see and the streets of the city connecting these, construct a list of trips fulfilling these conditions, or determine that it is impossible. Each trip must use at least one street, and there may be loops, i.e. streets with a start and end point in the same place.

-----Input-----
The first line of input consists of two integers $1\le N \le 100$ and $0 \le M \le 10000$, the number of places Emil wants to visit and the number of roads respectively. The places are numbered $0$ to $N-1$.

The next $M$ lines consists of two integers $0 \le f, t \le N-1$, denoting that there is a one-way street from place $f$ to place $t$.

-----Output-----
Output begins with an integer $N$ on its own line, the number of trips made. Then, for every trip, output a line with the number of places included in the trip $K$, followed by $K$ lines, containing the numbers of said places in order of visit (the last place which Emil returns to should not be output twice).

If the places can’t be split into trips, Emil instead goes bowling. Then just output the string "Yeah!". If there are several solutions, output any of them.

-----Examples-----
Sample Input 1:
4 4
0 1
1 0
2 3
3 2
Sample Output 1:
2
2
0
1
2
2
3

Sample Input 2:
4 4
0 1
1 0
2 3
3 3
Sample Output 2:
Yeah!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problem statements in [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a sequence $A_{1}, A_{2}, \ldots, A_{N}$. Chef wants you to handle $Q$ queries. There are two types of queries:
1 L R X: for each $i$ ($L ≤ i ≤ R$), add $(X + i - L)^2$ to $A_{i}$
2 Y: find the current value of $A_{Y}$

------  Input ------
The first line of the input contains two space-separated integers $N$ and $Q$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
$Q$ lines follow. Each of these lines describes a query in the format described above.

------  Output ------
For each query of the second type, print a single line containing one integer $A_{Y}$.

------  Constraints ------
$1 ≤ N, Q ≤ 10^{5}$
$0 ≤ |A_{i}| ≤ 10^{6}$ for each valid $i$
$1 ≤ L ≤ R ≤ N$
$0 ≤ |X| ≤ 10^{6}$
$1 ≤ Y ≤ N$

----- Sample Input 1 ------ 
5 4
1 10 3 6 5
1 1 3 5
2 3
1 4 5 7
2 5
----- Sample Output 1 ------ 
52
69
----- explanation 1 ------ 
- the sequence after the first query is $[1 + 5^{2}, 10 + (5 + 2 - 1)^2, 3 + (5 + 3 - 1)^2, 6, 5] = [26,  46, 52, 6, 5]$
- the second query asks for $A_{3}$, which is $52$
- the sequence after the third query is $[26,  46, 52, 6 + 7^{2}, 5 + (7+1)^2] = [26,  46, 52, 55, 69]$
- the fourth query asks for $A_{5}$, which is $69$

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The R1 company has recently bought a high rise building in the centre of Moscow for its main office. It's time to decorate the new office, and the first thing to do is to write the company's slogan above the main entrance to the building.

The slogan of the company consists of *n* characters, so the decorators hung a large banner, *n* meters wide and 1 meter high, divided into *n* equal squares. The first character of the slogan must be in the first square (the leftmost) of the poster, the second character must be in the second square, and so on.

Of course, the R1 programmers want to write the slogan on the poster themselves. To do this, they have a large (and a very heavy) ladder which was put exactly opposite the *k*-th square of the poster. To draw the *i*-th character of the slogan on the poster, you need to climb the ladder, standing in front of the *i*-th square of the poster. This action (along with climbing up and down the ladder) takes one hour for a painter. The painter is not allowed to draw characters in the adjacent squares when the ladder is in front of the *i*-th square because the uncomfortable position of the ladder may make the characters untidy. Besides, the programmers can move the ladder. In one hour, they can move the ladder either a meter to the right or a meter to the left.

Drawing characters and moving the ladder is very tiring, so the programmers want to finish the job in as little time as possible. Develop for them an optimal poster painting plan!

Input Specification:
The first line contains two integers, *n* and *k* (1<=≤<=*k*<=≤<=*n*<=≤<=100) — the number of characters in the slogan and the initial position of the ladder, correspondingly. The next line contains the slogan as *n* characters written without spaces. Each character of the slogan is either a large English letter, or digit, or one of the characters: '.', '!', ',', '?'.

Output Specification:
In *t* lines, print the actions the programmers need to make. In the *i*-th line print:
 -  "LEFT" (without the quotes), if the *i*-th action was "move the ladder to the left"; -  "RIGHT" (without the quotes), if the *i*-th action was "move the ladder to the right"; -  "PRINT *x*" (without the quotes), if the *i*-th action was to "go up the ladder, paint character *x*, go down the ladder". 
The painting time (variable *t*) must be minimum possible. If there are multiple optimal painting plans, you can print any of them.

Demo Input:
['2 2\nR1\n', '2 1\nR1\n', '6 4\nGO?GO!\n']

Demo Output:
['PRINT 1\nLEFT\nPRINT R\n', 'PRINT R\nRIGHT\nPRINT 1\n', 'RIGHT\nRIGHT\nPRINT !\nLEFT\nPRINT O\nLEFT\nPRINT G\nLEFT\nPRINT ?\nLEFT\nPRINT O\nLEFT\nPRINT G\n']

Note:
Note that the ladder cannot be shifted by less than one meter. The ladder can only stand in front of some square of the poster. For example, you cannot shift a ladder by half a meter and position it between two squares. Then go up and paint the first character and the second character.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nuske has a grid with N rows and M columns of squares. The rows are numbered 1 through N from top to bottom, and the columns are numbered 1 through M from left to right. Each square in the grid is painted in either blue or white. If S_{i,j} is 1, the square at the i-th row and j-th column is blue; if S_{i,j} is 0, the square is white. For every pair of two blue square a and b, there is at most one path that starts from a, repeatedly proceeds to an adjacent (side by side) blue square and finally reaches b, without traversing the same square more than once.

Phantom Thnook, Nuske's eternal rival, gives Q queries to Nuske. The i-th query consists of four integers x_{i,1}, y_{i,1}, x_{i,2} and y_{i,2} and asks him the following: when the rectangular region of the grid bounded by (and including) the x_{i,1}-th row, x_{i,2}-th row, y_{i,1}-th column and y_{i,2}-th column is cut out, how many connected components consisting of blue squares there are in the region?

Process all the queries.

Constraints

* 1 ≤ N,M ≤ 2000
* 1 ≤ Q ≤ 200000
* S_{i,j} is either 0 or 1.
* S_{i,j} satisfies the condition explained in the statement.
* 1 ≤ x_{i,1} ≤ x_{i,2} ≤ N(1 ≤ i ≤ Q)
* 1 ≤ y_{i,1} ≤ y_{i,2} ≤ M(1 ≤ i ≤ Q)

Input

The input is given from Standard Input in the following format:


N M Q
S_{1,1}..S_{1,M}
:
S_{N,1}..S_{N,M}
x_{1,1} y_{i,1} x_{i,2} y_{i,2}
:
x_{Q,1} y_{Q,1} x_{Q,2} y_{Q,2}


Output

For each query, print the number of the connected components consisting of blue squares in the region.

Examples

Input

3 4 4
1101
0110
1101
1 1 3 4
1 1 3 1
2 2 3 4
1 2 2 4


Output

3
2
2
2


Input

5 5 6
11010
01110
10101
11101
01010
1 1 5 5
1 2 4 5
2 3 3 4
3 3 3 3
3 1 3 5
1 1 3 4


Output

3
2
1
1
3
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
n people are standing in a line to play table tennis. At first, the first two players in the line play a game. Then the loser goes to the end of the line, and the winner plays with the next person from the line, and so on. They play until someone wins k games in a row. This player becomes the winner.

For each of the participants, you know the power to play table tennis, and for all players these values are different. In a game the player with greater power always wins. Determine who will be the winner.


-----Input-----

The first line contains two integers: n and k (2 ≤ n ≤ 500, 2 ≤ k ≤ 10^12) — the number of people and the number of wins.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ n) — powers of the player. It's guaranteed that this line contains a valid permutation, i.e. all a_{i} are distinct.


-----Output-----

Output a single integer — power of the winner.


-----Examples-----
Input
2 2
1 2

Output
2 
Input
4 2
3 1 2 4

Output
3 
Input
6 2
6 5 3 1 2 4

Output
6 
Input
2 10000000000
2 1

Output
2



-----Note-----

Games in the second sample:

3 plays with 1. 3 wins. 1 goes to the end of the line.

3 plays with 2. 3 wins. He wins twice in a row. He becomes the winner.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N pinholes on the xy-plane. The i-th pinhole is located at (x_i,y_i).

We will denote the Manhattan distance between the i-th and j-th pinholes as d(i,j)(=|x_i-x_j|+|y_i-y_j|).

You have a peculiar pair of compasses, called Manhattan Compass. This instrument always points at two of the pinholes. The two legs of the compass are indistinguishable, thus we do not distinguish the following two states: the state where the compass points at the p-th and q-th pinholes, and the state where it points at the q-th and p-th pinholes.

When the compass points at the p-th and q-th pinholes and d(p,q)=d(p,r), one of the legs can be moved so that the compass will point at the p-th and r-th pinholes.

Initially, the compass points at the a-th and b-th pinholes. Find the number of the pairs of pinholes that can be pointed by the compass.

Constraints

* 2≦N≦10^5
* 1≦x_i, y_i≦10^9
* 1≦a < b≦N
* When i ≠ j, (x_i, y_i) ≠ (x_j, y_j)
* x_i and y_i are integers.

Input

The input is given from Standard Input in the following format:


N a b
x_1 y_1
:
x_N y_N


Output

Print the number of the pairs of pinholes that can be pointed by the compass.

Examples

Input

5 1 2
1 1
4 3
6 1
5 5
4 8


Output

4


Input

6 2 3
1 3
5 3
3 5
8 4
4 7
2 5


Output

4


Input

8 1 2
1 5
4 3
8 2
4 7
8 8
3 3
6 6
4 8


Output

7

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have *n* problems. You have estimated the difficulty of the *i*-th one as integer *c**i*. Now you want to prepare a problemset for a contest, using some of the problems you've made.

A problemset for the contest must consist of at least two problems. You think that the total difficulty of the problems of the contest must be at least *l* and at most *r*. Also, you think that the difference between difficulties of the easiest and the hardest of the chosen problems must be at least *x*.

Find the number of ways to choose a problemset for the contest.

Input Specification:
The first line contains four integers *n*, *l*, *r*, *x* (1<=≤<=*n*<=≤<=15, 1<=≤<=*l*<=≤<=*r*<=≤<=109, 1<=≤<=*x*<=≤<=106) — the number of problems you have, the minimum and maximum value of total difficulty of the problemset and the minimum difference in difficulty between the hardest problem in the pack and the easiest one, respectively.

The second line contains *n* integers *c*1,<=*c*2,<=...,<=*c**n* (1<=≤<=*c**i*<=≤<=106) — the difficulty of each problem.

Output Specification:
Print the number of ways to choose a suitable problemset for the contest.

Demo Input:
['3 5 6 1\n1 2 3\n', '4 40 50 10\n10 20 30 25\n', '5 25 35 10\n10 10 20 10 20\n']

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

Note:
In the first example two sets are suitable, one consisting of the second and third problem, another one consisting of all three problems.

In the second example, two sets of problems are suitable — the set of problems with difficulties 10 and 30 as well as the set of problems with difficulties 20 and 30.

In the third example any set consisting of one problem of difficulty 10 and one problem of difficulty 20 is suitable.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are on your way to your first job interview as a program tester, and you are already late. The interview is in a skyscraper and you are currently in floor $s$, where you see an elevator. Upon entering the elvator, you learn that it has only two buttons, marked “UP $u$” and “DOWN$d$”. You conclude that the UP-button takes the elevator $u$ floors up (if there aren’t enough floors, pressing the UP-botton does nothing, or at least so you assume), whereas the DOWN-button takes you $d$ stories down (or none if there aren’t enough). Knowing that the interview is at floor $g$, and that there are only $f$ floors in the building, you quickly decide to write a program that gives you the amount of button pushes you need to perform. If you simply cannot reach the correct floor, your program halts with the message “use the stairs”.

Given input $f$, $s$, $g$, $u$ and $d$ (floors, start, goal, up, down), find the shortest sequence of button presses you must press in order to get from $s$ to $g$, given a building of $f$ floors, or output “use the stairs” if you cannot get from $s$ to $g$ by the given elevator.

-----Input-----
The input will consist of one line with the five integers $f$, $s$, $g$, $u$, and $d$, where $1 \leq s,g \leq f \leq 1000000$ and $0 \leq u,d \leq 1000000$. The floors are one-indexed, i.e., if there are 10 stories, $s$ and $g$ are between $1$ and $10$ (inclusive).

-----Output-----
Output the minimum numbers of pushes you must make in order to get from $s$ to $g$, or output use the stairs if it is impossible given the configuration of the elvator.

-----Examples-----
Sample Input:
10 1 10 2 1
Sample Output:
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef likes to play with array elements. His teacher has given him an array problem. But now he is busy as Christmas is coming. So, he needs your help. Can you help him to solve this problem.
You are given an array $(A1,A2,A3……AN)$ of length $N$. You have to create an another array using the given array in the following ways:

For each valid i, the ith element of the output array will be the sum of the ith element and (A[i])th element if $A[i]$ is less equal $N$.

Other wise for each valid i following the step below

i) Divide the value of $A[i]$ by 2 untill it will be less than$N$.

ii) then find the difference ($D$) between $N$ and $A[i]$.

iii) the ith element of the output array will be $Dth$ element.  

-----Input:-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of T test cases follows.  
- The first line of each test case contains a single integer $N$.  
- The second line contains $N$ space-separated integers $A1,A2,…,AN$.   

-----Output:-----
- For each testcase, print new array in each line.

-----Constraints-----
- $1 \leq T \leq 1000$
- $1 \leq N \leq 10^5$
- $1\leq A1,A2.....AN \leq 10^7$

-----Sample Input:-----
2

5

2 4 5 7 9

4

5 4 2 3

-----Sample Output:-----
6 11 14 4 2

4 7 6 5

-----EXPLANATION:-----
For 1st test case: A1 = 2+4 =6, A2 = 4+7 =11 , A3 = 5+9 =14 , A4 > N (5) ,So A4/2 = 3 then A4 = A[5 -3] , A4=A[2]=4, And A5 =A[1]=2. Then array becomes 6,11,14,4,2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Again Twenty Five!

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The HR manager was disappointed again. The last applicant failed the interview the same way as 24 previous ones. "Do I give such a hard task?" — the HR manager thought. "Just raise number 5 to the power of *n* and get last two digits of the number. Yes, of course, *n* can be rather big, and one cannot find the power using a calculator, but we need people who are able to think, not just follow the instructions."

Could you pass the interview in the machine vision company in IT City?

Input Specification:
The only line of the input contains a single integer *n* (2<=≤<=*n*<=≤<=2·1018) — the power in which you need to raise number 5.

Output Specification:
Output the last two digits of 5*n* without spaces between them.

Demo Input:
['2\n']

Demo Output:
['25']

Note:
none

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