vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You're given an ancient book that unfortunately has a few pages in the wrong position, fortunately your computer has a list of every page number in order from ``1`` to ``n``.

You're supplied with an array of numbers, and should return an array with each page number that is out of place. Incorrect page numbers will not appear next to each other. Duplicate incorrect page numbers are possible.

Example:

```Given: list = [1,2,10,3,4,5,8,6,7]
```

``Return: [10,8]
``

Your returning list should have the incorrect page numbers in the order they were found.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi will do a tap dance. The dance is described by a string S where each character is L, R, U, or D. These characters indicate the positions on which Takahashi should step. He will follow these instructions one by one in order, starting with the first character.
S is said to be easily playable if and only if it satisfies both of the following conditions:
 - Every character in an odd position (1-st, 3-rd, 5-th, \ldots) is R, U, or D.
 - Every character in an even position (2-nd, 4-th, 6-th, \ldots) is L, U, or D.
Your task is to print Yes if S is easily playable, and No otherwise.

-----Constraints-----
 - S is a string of length between 1 and 100 (inclusive).
 - Each character of S is L, R, U, or D.

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print Yes if S is easily playable, and No otherwise.

-----Sample Input-----
RUDLUDR

-----Sample Output-----
Yes

Every character in an odd position (1-st, 3-rd, 5-th, 7-th) is R, U, or D.
Every character in an even position (2-nd, 4-th, 6-th) is L, U, or D.
Thus, S is easily playable.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hattori is very much inspired by the way GMAIL works. He decides to build his own simple version of GMAIL. He divides the mails into 3 categories ,namely : UNREAD , READ and TRASH.
UNREAD:the messages that haven't been read.
READ:The messages that is read by the user.
TRASH: The messages deleted by the user.
Now, At any point of time, The user can READ an UNREAD message , Move an UNREAD message to TRASH , Move a READ message to TRASH or restore a deleted message back to READ category.Now , Hattori requires your help in determining the messages left in all the categories aligned in the order of their arrival in that category.
Formally: You are given N messages , with ID from 1 to N. Initially all the messages are in the UNREAD section of the mail.Now, Q queries are given in the form as shown below:
1 X : Move the message with ID X from UNREAD to READ.
2 X : Move the message with ID X from READ to TRASH.
3 X : Move the message with ID X from UNREAD to TRASH.
4 X : Move the message with ID X from TRASH to READ.
Given that all the queries are valid, Help Hattori in Determining the messages in all the 3 sections. There are N mails initially having id's from 1 to N. Then there are total Q querieseach in the form mentioned in the question. The queries are mentioned in a list query where ith query is represented by (2*i)thand (2*i+1)th value of the list.Example 1:Input: N = 10, Q = 7query = {1, 2, 1, 5, 1, 7, 1, 9,         2, 5, 2, 7, 4, 5}Output: UNREAD - 1 3 4 6 8 10READ - 2 9 5TRASH - 7Explaination: Initial:UNREAD section: 1 2 3 4 5 6 7 8 9 10READ section : EMPTYTRASH section : EmptyQuery 1 : 1 2UNREAD section: 1 3 4 5 6 7 8 9 10READ section : 2TRASH section : EmptyQuery 2 : 1 5UNREAD section: 1 3 4 6 7 8 9 10READ section : 2 5TRASH section : EmptyQuery 3 : 1 7UNREAD section: 1 3 4 6 8 9 10READ section : 2 5 7TRASH section : EmptyQuery 4 : 1 9UNREAD section: 1 3 4 6 8 10READ section : 2 5 7 9TRASH section : EmptyQuery 5 : 2 5UNREAD section: 1 3 4 6 8 10READ section : 2 7 9TRASH section : 5Query 6 : 2 7UNREAD section: 1 3 4 6 8 10READ section : 2 9TRASH section : 5 7Query 7 : 4 5UNREAD section: 1 3 4 6 8 10READ section : 2 9 5TRASH section : 7Your Task:
You do not need to read input or print anyting. Your task is to complete the function mailDesign() which takes N, Q and query as input parameters and returns a list containing the starting pointer of the three linked lists unread, read and trash. If any linked list is empty pass a null pointer as the head of that list.Expected Time Complexity: O(Q*N)
Expected Auxiliary Space: O(N)Constraints:
1 < N, Q < 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Note that the differences between easy and hard versions are the constraints on n and the time limit. You can make hacks only if both versions are solved.

AquaMoon knew through foresight that some ghosts wanted to curse tourists on a pedestrian street. But unfortunately, this time, these ghosts were hiding in a barrier, and she couldn't enter this barrier in a short time and destroy them. Therefore, all that can be done is to save any unfortunate person on the street from the ghosts.

The pedestrian street can be represented as a one-dimensional coordinate system. There is one person hanging out on the pedestrian street. At the time 0 he is at coordinate x, moving with a speed of 1 unit per second. In particular, at time i the person will be at coordinate x+i.

The ghosts are going to cast n curses on the street. The i-th curse will last from time tl_i-1+10^{-18} to time tr_i+1-10^{-18} (exclusively) and will kill people with coordinates from l_i-1+10^{-18} to r_i+1-10^{-18} (exclusively). Formally that means, that the person, whose coordinate is between (l_i-1+10^{-18},r_i+1-10^{-18}) in the time range (tl_i-1+10^{-18},tr_i+1-10^{-18}) will die.

To save the person on the street, AquaMoon can stop time at any moment t, and then move the person from his current coordinate x to any coordinate y (t, x and y are not necessarily integers). The movement costs AquaMoon |x-y| energy. The movement is continuous, so if there exists some cursed area between points x and y at time t, the person will die too.

AquaMoon wants to know what is the minimum amount of energy she needs to spend in order to save the person on the street from all n curses. But she is not good at programming. As her friend, can you help her?

Input

The first line contains a single integer n (1≤ n≤ 2 ⋅ 10^5) — the number of curses.

The next line contains a single integer x (1≤ x≤ 10^6) — the initial coordinate of the person.

The following n lines contain four integers tl_i, tr_i, l_i, r_i each (1≤ tl_i≤ tr_i≤ 10^6, 1≤ l_i≤ r_i≤ 10^6).

Output

Print a single integer — the minimum energy which AquaMoon needs to spent, rounded up to the nearest integer (in case there are two nearest integers you should round the answer to the highest of them).

Examples

Input


2
1
1 2 1 2
2 3 2 3


Output


2

Input


3
4
1 4 1 2
1 4 4 15
6 7 1 4


Output


8

Input


4
3
1 5 1 1
4 10 1 4
1 2 3 13
1 10 7 19


Output


14

Input


7
5
78 96 76 91
6 16 18 37
53 63 40 56
83 88 21 38
72 75 17 24
63 63 53 60
34 46 60 60


Output


20

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got two rectangular tables with sizes *n**a*<=×<=*m**a* and *n**b*<=×<=*m**b* cells. The tables consist of zeroes and ones. We will consider the rows and columns of both tables indexed starting from 1. Then we will define the element of the first table, located at the intersection of the *i*-th row and the *j*-th column, as *a**i*,<=*j*; we will define the element of the second table, located at the intersection of the *i*-th row and the *j*-th column, as *b**i*,<=*j*. 

We will call the pair of integers (*x*,<=*y*) a shift of the second table relative to the first one. We'll call the overlap factor of the shift (*x*,<=*y*) value:

where the variables *i*,<=*j* take only such values, in which the expression *a**i*,<=*j*·*b**i*<=+<=*x*,<=*j*<=+<=*y* makes sense. More formally, inequalities 1<=≤<=*i*<=≤<=*n**a*,<=1<=≤<=*j*<=≤<=*m**a*,<=1<=≤<=*i*<=+<=*x*<=≤<=*n**b*,<=1<=≤<=*j*<=+<=*y*<=≤<=*m**b* must hold. If there are no values of variables *i*,<=*j*, that satisfy the given inequalities, the value of the sum is considered equal to 0. 

Your task is to find the shift with the maximum overlap factor among all possible shifts.

Input Specification:
The first line contains two space-separated integers *n**a*,<=*m**a* (1<=≤<=*n**a*,<=*m**a*<=≤<=50) — the number of rows and columns in the first table. Then *n**a* lines contain *m**a* characters each — the elements of the first table. Each character is either a "0", or a "1".

The next line contains two space-separated integers *n**b*,<=*m**b* (1<=≤<=*n**b*,<=*m**b*<=≤<=50) — the number of rows and columns in the second table. Then follow the elements of the second table in the format, similar to the first table.

It is guaranteed that the first table has at least one number "1". It is guaranteed that the second table has at least one number "1".

Output Specification:
Print two space-separated integers *x*,<=*y* (|*x*|,<=|*y*|<=≤<=109) — a shift with maximum overlap factor. If there are multiple solutions, print any of them.

Demo Input:
['3 2\n01\n10\n00\n2 3\n001\n111\n', '3 3\n000\n010\n000\n1 1\n1\n']

Demo Output:
['0 1\n', '-1 -1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A company needs random numbers for its operation. $N$ random numbers have been generated using $N$ numbers as seeds and the following recurrence formula:

$\begin{aligned}F(K)=&\left(C(1)\times F(K-1)+C(2)\times F(K-2)+\cdots+C(N-1)\times F(K-N+1)+C(N)\times F(K-N)\right)\text{\%}\left(10^9+7\right)\end{aligned}$

The numbers used as seeds are $F(N-1),F(N-2),...,F(1),F(0)$. $F(K)$ is the $K^{\mbox{th}}$ term of the recurrence.

Due to a failure on the servers, the company lost its seed numbers. Now they just have the recurrence formula and the previously generated $N$ random numbers.

The company wants to recover the numbers used as seeds, so they have hired you for doing this task.

Input Format

The first line contains two space-separated integers, $N$ and $\mbox{K}$, respectively. 

The second line contains the space-separated integers describing $F(K),F(K-1),...,F(K-N+2),F(K-N+1)$ (all these numbers are non-negative integers $<10^9$). 

The third line contains the space-separated coefficients of the recurrence formula, $C(1),C(2),...,C(N-1),C(N)$. All of these coefficients are positive integers $<10^9$.

Constraints

$1\leq N\leq50$
$1\leq K\leq10^9$
$0\leq K-N+1$

Output Format

The output must be one line containing the space-separated seeds of the random numbers - $F(N-1),F(N-2),...,F(1),F(0)$.

Sample Input
2 6
13 8
1 1

Sample Output
1 1 

Explanation

This is the classic Fibonacci recurrence. We have the $6^{th}$ and $5^{th}$ terms, and, of course, the seeds are the numbers $1$ and $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bachgold problem is very easy to formulate. Given a positive integer n represent it as a sum of maximum possible number of prime numbers. One can prove that such representation exists for any integer greater than 1.

Recall that integer k is called prime if it is greater than 1 and has exactly two positive integer divisors — 1 and k. 

Input

The only line of the input contains a single integer n (2 ≤ n ≤ 100 000).

Output

The first line of the output contains a single integer k — maximum possible number of primes in representation.

The second line should contain k primes with their sum equal to n. You can print them in any order. If there are several optimal solution, print any of them.

Examples

Input

5


Output

2
2 3


Input

6


Output

3
2 2 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string S of length N consisting of A, C, G and T. Answer the following Q queries:
 - Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does AC occurs as a substring?

-----Notes-----
A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T.
For example, the substrings of ATCODER include TCO, AT, CODER, ATCODER and  (the empty string), but not AC.

-----Constraints-----
 - 2 \leq N \leq 10^5
 - 1 \leq Q \leq 10^5
 - S is a string of length N.
 - Each character in S is A, C, G or T.
 - 1 \leq l_i < r_i \leq N

-----Input-----
Input is given from Standard Input in the following format:
N Q
S
l_1 r_1
:
l_Q r_Q

-----Output-----
Print Q lines. The i-th line should contain the answer to the i-th query.

-----Sample Input-----
8 3
ACACTACG
3 7
2 3
1 8

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

 - Query 1: the substring of S starting at index 3 and ending at index 7 is ACTAC. In this string, AC occurs twice as a substring.
 - Query 2: the substring of S starting at index 2 and ending at index 3 is CA. In this string, AC occurs zero times as a substring.
 - Query 3: the substring of S starting at index 1 and ending at index 8 is ACACTACG. In this string, AC occurs three times as a substring.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pay attention: this problem is interactive.

Penguin Xoriy came up with a new game recently. He has n icicles numbered from 1 to n. Each icicle has a temperature — an integer from 1 to 109. Exactly two of these icicles are special: their temperature is y, while a temperature of all the others is x ≠ y. You have to find those special icicles. You can choose a non-empty subset of icicles and ask the penguin what is the bitwise exclusive OR (XOR) of the temperatures of the icicles in this subset. Note that you can't ask more than 19 questions.

You are to find the special icicles.

Input

The first line contains three integers n, x, y (2 ≤ n ≤ 1000, 1 ≤ x, y ≤ 109, x ≠ y) — the number of icicles, the temperature of non-special icicles and the temperature of the special icicles.

Output

To give your answer to the penguin you have to print character "!" (without quotes), then print two integers p1, p2 (p1 < p2) — the indexes of the special icicles in ascending order. Note that "!" and p1 should be separated by a space; the indexes should be separated by a space too. After you gave the answer your program should terminate immediately.

Interaction

To ask a question print character "?" (without quotes), an integer c (1 ≤ c ≤ n), and c distinct integers p1, p2, ..., pc (1 ≤ pi ≤ n) — the indexes of icicles that you want to know about. Note that "?" and c should be separated by a space; the indexes should be separated by a space too.

After you asked the question, read a single integer — the answer.

Note that you can't ask more than 19 questions. If you ask more than 19 questions or at least one incorrect question, your solution will get "Wrong answer".

If at some moment your program reads  - 1 as an answer, it should immediately exit (for example, by calling exit(0)). You will get "Wrong answer" in this case, it means that you asked more than 19 questions, or asked an invalid question. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.

Your solution will get "Idleness Limit Exceeded", if you don't print anything or forget to flush the output, including for the final answer .

To flush you can use (just after printing): 

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



Hacking

For hacking use the following format:

n x y p1 p2

Here 1 ≤ p1 < p2 ≤ n are the indexes of the special icicles.

Contestant programs will not be able to see this input.

Example

Input

4 2 1
2
1
1<span class="tex-font-style-it"></span>

Output

? 3 1 2 3
? 1 1
? 1 3
! 1 3

Note

The answer for the first question is <image>.

The answer for the second and the third questions is 1, therefore, special icicles are indexes 1 and 3.

You can read more about bitwise XOR operation here: <https://en.wikipedia.org/wiki/Bitwise_operation#XOR>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the evenings Donkey would join Shrek to look at the stars. They would sit on a log, sipping tea and they would watch the starry sky. The sky hung above the roof, right behind the chimney. Shrek's stars were to the right of the chimney and the Donkey's stars were to the left. Most days the Donkey would just count the stars, so he knew that they are exactly n. This time he wanted a challenge. He imagined a coordinate system: he put the origin of the coordinates at the intersection of the roof and the chimney, directed the OX axis to the left along the roof and the OY axis — up along the chimney (see figure). The Donkey imagined two rays emanating from he origin of axes at angles α_1 and α_2 to the OX axis.

 [Image] 

Now he chooses any star that lies strictly between these rays. After that he imagines more rays that emanate from this star at the same angles α_1 and α_2 to the OX axis and chooses another star that lies strictly between the new rays. He repeats the operation as long as there still are stars he can choose between the rays that emanate from a star. 

 [Image] 

As a result, the Donkey gets a chain of stars. He can consecutively get to each star if he acts by the given rules.

Your task is to find the maximum number of stars m that the Donkey's chain can contain.

Note that the chain must necessarily start in the point of the origin of the axes, that isn't taken into consideration while counting the number m of stars in the chain.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of stars. The second line contains simple fractions representing relationships "a/b c/d", such that $\frac{a}{b} = \frac{\operatorname{sin} \alpha_{1}}{\operatorname{cos} \alpha_{1}}$ and $\frac{c}{d} = \frac{\operatorname{sin} \alpha_{2}}{\operatorname{cos} \alpha}$ (0 ≤ a, b, c, d ≤ 10^5; $0^{\circ} \leq \alpha_{1} < \alpha_{2} \leq 90^{\circ}$; $\frac{a}{b} \neq \frac{0}{0}$; $\frac{c}{d} \neq \frac{0}{0}$). The given numbers a, b, c, d are integers.

Next n lines contain pairs of integers x_{i}, y_{i} (1 ≤ x_{i}, y_{i} ≤ 10^5)— the stars' coordinates.

It is guaranteed that all stars have distinct coordinates.


-----Output-----

In a single line print number m — the answer to the problem.


-----Examples-----
Input
15
1/3 2/1
3 1
6 2
4 2
2 5
4 5
6 6
3 4
1 6
2 1
7 4
9 3
5 3
1 3
15 5
12 4

Output
4



-----Note-----

In the sample the longest chain the Donkey can build consists of four stars. Note that the Donkey can't choose the stars that lie on the rays he imagines.

 [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. A and Mr. B live in an N × M rectangular grid area. Each square is either a road, a wall, or a house. Since this area is famous for the frequent occurrence of molestation damage due to the complicated and intricate roads, the boundary between this area and the outside is completely surrounded by walls and isolated.

Mr. B somehow felt like it, so he decided to go to see Mr. A's house. However, unfortunately, Mr. B has an apparently suspicious face, so if he takes any action that seems to be suspected of being a molester on his way to Mr. A's house, he will be caught immediately. In particular, never walk with your right hand off the wall. Can Mr. B reach Mr. A's house without letting go of his right hand for a moment?

Mr. B is always facing up, down, left, or right, and the range that Mr. B's right hand can reach is only four squares, front, diagonally right front, right, and diagonally right back with respect to the direction that Mr. B is facing. Mr. B repeats one of the following actions. However, these cannot be done at the same time.

* If there is no wall in front, go one square.
* Change the direction you are facing to the right by 90 degrees.
* Change the direction you are facing to the left by 90 degrees.
* Change the square that your right hand touches. However, at this time, Mr. B cannot release his right hand, so he must have something in common between the square before the change and the square after the change.

Constraints

* 1 ≤ N ≤ 50
* 1 ≤ M ≤ 50
* Only one of the characters "^", "v", "<", ">" always appears in the input.
* Similarly, only one letter "G" always appears in the input.
* In the initial state, Mr. B's right hand touches the wall on the right from the direction in which Mr. B is facing.

Input

The input is given in the following format.


N M
S1
S2
::
SN


Si (1 ≤ i ≤ N) is a string of M characters, each character representing the following.

* "^", "V", "<", ">" indicate the first position of Mr. B and the direction (up, down, left, right).
* "." Is an empty cell. Mr. B can move on this square.
* "#" Represents a wall. You cannot move on the wall.
* "G" represents the location of Mr. A's house. Mr. B repeats the movement until he reaches Mr. A's house.

Output

If you can reach Mr. A's house without releasing your right hand, output the minimum number of different squares that you have passed to reach Mr. A's house. If you cannot reach Mr. A's house, output -1.

Examples

Input

3 3
G##
.#.
.


Output

4


Input

3 3
G##
.#.
.<.


Output

4


Input

3 3
G##
.#.
.>.


Output

6


Input

3 3
...
.G.
.>.


Output

-1


Input

4 4
....
.#.G
...#
^#..


Output

8

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

You are given a positive integer `n`. We intend to make some ascending sequences according to the following rules:

 1. Make a sequence of length 1: [ n ]

 2. Or, insert a number to the left side of the sequence. But this number can not exceed half of the first number of the sequence. 

 3. Follow rule 2, continue insert number to the left side of the sequence.

Your task is to count the number of all possible sequences, and return it.

If you do not understand the task, please read the rewritten version below:

You are given a positive integer `n`. Your task is to count the number of such sequences: 

- It should be an ascending sequence;

- It should end with number `n`.

- Each number in the sequence should smaller or equals to the half of its right, except for the last number `n`.

- We define that a sequence containing only a number `n` is a valid ascending sequence.

# Examples

For `n = 6`, the output should be `6`.

All sequences we made are:

```
[6]

insert a number to the left:

[1,6]
[2,6]
[3,6]

continue insert number:

[1,2,6]
[1,3,6]
```
There are 6 sequences in total.


For `n = 10`, the output should be `14`.

All sequences we made are:

```
[10]

insert a number to the left:

[1,10]
[2,10]
[3,10]
[4,10]
[5,10]

continue insert number:

[1,2,10]
[1,3,10]
[1,4,10]
[2,4,10]
[1,5,10]
[2,5,10]

continue insert number:

[1,2,4,10]
[1,2,5,10]

```
There are 14 sequences in total.

# Note

- `1 <= n <= 1000`

- `3` fixed testcases

- `100` random testcases, testing for correctness of solution

- All inputs are valid.

- If my reference solution gives the wrong result in the random tests, please let me know(post an issue).

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