vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an NxM chessboard. Find the number of pairs of different positions of a bishop and a PQ-knight where they don't attack each other modulo 10^9 + 7.

A bishop can move to square if it's on the same diagonal with it.

A PQ-knight with given integers P and Q (P doesn't equals Q) can move to the square if the move forms "L-shape": P squares vertically and Q squares horizontally, or Q squares horizontally and P squares vertically. Note that if P = 1 and Q = 2, or P = 2 and Q = 1 it's a usual chess knight.

Input
The only line of the input contains 4 space-separated integers: N, M, P, Q

Output
Output one integer - the answer for the question modulo 10^9 + 7.

Constraints 
0  < N, M, P, Q ≤ 10^9, P never equals Q.
N, M ≤ 30 in 40% of the test data.
N, M ≤ 10^6 in 65% of the test data.

SAMPLE INPUT
2 5 1 2

SAMPLE OUTPUT
62

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:


    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
    ...


Example 1:


Input: "A"
Output: 1


Example 2:


Input: "AB"
Output: 28


Example 3:


Input: "ZY"
Output: 701

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The ancient and mysterious Apaxian civilization, which we most certainly did not make up, continues to confound the researchers at the Oriental Institute. It turns out that the Apaxians had a peculiar naming system: the more letters in your name, the higher your status in society. So, in Apaxian society, robert was probably a lowly servant, and robertapalaxiamethostenes was likely a High Priest or Minister. Even more than that, Apaxians valued the number of adjacent letters that were the same in a name. So, while robert continues to be an unimpressive name, roooooooooobert probably elicited cheers and applause wherever he went.

Unfortunately, this makes the task of reading Apaxian scrolls very cumbersome, especially when you consider that a particularly famous Apaxian queen had ten thousand consecutive a’s in her name. Legend has it that she was already two years old by the time the Royal Herald finished announcing her birth.

To make the Oriental Institute’s life easier, the Department of Computer Science has offered to convert the Apaxian scrolls into a more readable format. Specifically, we will be taking Apaxian names and replacing all consecutive runs of the same letter by a single instance of such letter.

So, for example, the compact version of roooobert would be robert, where the four consecutive o’s have been replaced with a single o. Similarly, the compact version of rrrooobbbert would also be robert. On the other hand, the compact version of robert is still robert.

-----Input-----
The input contains a single name. Each name contains only lowercase letters (a–z), no whitespace, a minimum length of 1 character, and a maximum length of 250 characters.

-----Output-----
The output contains the compact version of the name: any time the same letter appears two or more times in sequence, it must be replaced by a single instance of that letter.

-----Examples-----
Sample Input 1:
robert
Sample Output 1:
robert

Sample Input 2:
rooobert
Sample Output 2:
robert

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

It's the end of July – the time when a festive evening is held at Jelly Castle! Guests from all over the kingdom gather here to discuss new trends in the world of confectionery. Yet some of the things discussed here are not supposed to be disclosed to the general public: the information can cause discord in the kingdom of Sweetland in case it turns out to reach the wrong hands. So it's a necessity to not let any uninvited guests in.

There are 26 entrances in Jelly Castle, enumerated with uppercase English letters from A to Z. Because of security measures, each guest is known to be assigned an entrance he should enter the castle through. The door of each entrance is opened right before the first guest's arrival and closed right after the arrival of the last guest that should enter the castle through this entrance. No two guests can enter the castle simultaneously.

For an entrance to be protected from possible intrusion, a candy guard should be assigned to it. There are k such guards in the castle, so if there are more than k opened doors, one of them is going to be left unguarded! Notice that a guard can't leave his post until the door he is assigned to is closed.

Slastyona had a suspicion that there could be uninvited guests at the evening. She knows the order in which the invited guests entered the castle, and wants you to help her check whether there was a moment when more than k doors were opened.


-----Input-----

Two integers are given in the first string: the number of guests n and the number of guards k (1 ≤ n ≤ 10^6, 1 ≤ k ≤ 26).

In the second string, n uppercase English letters s_1s_2... s_{n} are given, where s_{i} is the entrance used by the i-th guest.


-----Output-----

Output «YES» if at least one door was unguarded during some time, and «NO» otherwise.

You can output each letter in arbitrary case (upper or lower).


-----Examples-----
Input
5 1
AABBB

Output
NO

Input
5 1
ABABB

Output
YES



-----Note-----

In the first sample case, the door A is opened right before the first guest's arrival and closed when the second guest enters the castle. The door B is opened right before the arrival of the third guest, and closed after the fifth one arrives. One guard can handle both doors, as the first one is closed before the second one is opened.

In the second sample case, the door B is opened before the second guest's arrival, but the only guard can't leave the door A unattended, as there is still one more guest that should enter the castle through this door.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Btoh yuo adn yuor roomatme lhoate wianshg disehs, btu stlil sdmoeboy msut peorrfm tihs cohre dialy. Oen dya yuo decdie to idourtcne smoe syestm. Yuor rmmotaoe sstgegus teh fooniwllg dael. Yuo argee on tow arayrs of ientgres M adn R, nmebur upmicnog dyas (induiclng teh cunrret oen) wtih sicsescuve irnegets (teh ceurrnt dya is zreo), adn yuo wsah teh diehss on dya D if adn olny if terhe etsixs an iednx i scuh taht D mod M[i] = R[i], otwsehrie yuor rmootmae deos it. Yuo lkie teh cncepot, btu yuor rmotaome's cuinnng simle meaks yuo ssecupt sthnoemig, so yuo itennd to vefriy teh fnerisas of teh aemnrgeet.

Yuo aer geivn ayarrs M adn R. Cuaclatle teh pceanregte of dyas on wchih yuo edn up dnoig teh wisahng. Amsuse taht yuo hvae iiiftlneny mnay dyas aehad of yuo. 


-----Input-----

The first line of input contains a single integer N (1 ≤ N ≤ 16).

The second and third lines of input contain N integers each, all between 0 and 16, inclusive, and represent arrays M and R, respectively. All M[i] are positive, for each i R[i] < M[i].


-----Output-----

Output a single real number. The answer is considered to be correct if its absolute or relative error does not exceed 10^{ - 4}.


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

Output
0.500000

Input
2
2 3
1 0

Output
0.666667

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Память компьютера состоит из n ячеек, которые выстроены в ряд. Пронумеруем ячейки от 1 до n слева направо. Про каждую ячейку известно, свободна она или принадлежит какому-либо процессу (в таком случае известен процесс, которому она принадлежит).

Для каждого процесса известно, что принадлежащие ему ячейки занимают в памяти непрерывный участок. С помощью операций вида «переписать данные из занятой ячейки в свободную, а занятую теперь считать свободной» требуется расположить все принадлежащие процессам ячейки в начале памяти компьютера. Другими словами, любая свободная ячейка должна располагаться правее (иметь больший номер) любой занятой.

Вам необходимо найти минимальное количество операций переписывания данных из одной ячейки в другую, с помощью которых можно достичь описанных условий. Допустимо, что относительный порядок ячеек в памяти для каждого из процессов изменится после дефрагментации, но относительный порядок самих процессов должен остаться без изменений. Это значит, что если все ячейки, принадлежащие процессу i, находились в памяти раньше всех ячеек процесса j, то и после перемещений это условие должно выполняться.

Считайте, что номера всех процессов уникальны, хотя бы одна ячейка памяти занята каким-либо процессом.


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

В первой строке входных данных записано число n (1 ≤ n ≤ 200 000) — количество ячеек в памяти компьютера.

Во второй строке входных данных следуют n целых чисел a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ n), где a_{i} равно либо 0 (это означает, что i-я ячейка памяти свободна), либо номеру процесса, которому принадлежит i-я ячейка памяти. Гарантируется, что хотя бы одно значение a_{i} не равно 0.

Процессы пронумерованы целыми числами от 1 до n в произвольном порядке. При этом процессы не обязательно пронумерованы последовательными числами.


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

Выведите одно целое число — минимальное количество операций, которое нужно сделать для дефрагментации памяти.


-----Примеры-----
Входные данные
4
0 2 2 1

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

Входные данные
8
0 8 8 8 0 4 4 2

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



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

В первом тестовом примере достаточно двух операций:  Переписать данные из третьей ячейки в первую. После этого память компьютера примет вид: 2 2 0 1.  Переписать данные из четвертой ячейки в третью. После этого память компьютера примет вид: 2 2 1 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The dragon's curve is a self-similar fractal which can be obtained by a recursive method. 

Starting with the string `D0 = 'Fa'`, at each step simultaneously perform the following operations:

```
replace 'a' with: 'aRbFR'
replace 'b' with: 'LFaLb'
```

For example (spaces added for more visibility) : 

```
1st iteration: Fa -> F aRbF R
2nd iteration: FaRbFR -> F aRbFR R LFaLb FR
```

After `n` iteration, remove `'a'` and `'b'`. You will have a string with `'R'`,`'L'`, and `'F'`. This is a set of instruction. Starting at the origin of a grid looking in the `(0,1)` direction, `'F'` means a step forward, `'L'` and `'R'` mean respectively turn left and right. After executing all instructions, the trajectory will give a beautifull self-replicating pattern called 'Dragon Curve'

The goal of this kata is to code a function wich takes one parameter `n`, the number of iterations needed and return the string of instruction as defined above. For example: 

```
n=0, should return: 'F'
n=1, should return: 'FRFR'
n=2, should return: 'FRFRRLFLFR'
```

`n` should be a number and non-negative integer. All other case should return the empty string: `''`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A social network for dogs called DH (DogHouse) has k special servers to recompress uploaded videos of cute cats. After each video is uploaded, it should be recompressed on one (any) of the servers, and only after that it can be saved in the social network.

We know that each server takes one second to recompress a one minute fragment. Thus, any server takes m seconds to recompress a m minute video.

We know the time when each of the n videos were uploaded to the network (in seconds starting from the moment all servers started working). All videos appear at different moments of time and they are recompressed in the order they appear. If some video appeared at time s, then its recompressing can start at that very moment, immediately. Some videos can await recompressing when all the servers are busy. In this case, as soon as a server is available, it immediately starts recompressing another video. The videos that await recompressing go in a queue. If by the moment the videos started being recompressed some servers are available, then any of them starts recompressing the video.

For each video find the moment it stops being recompressed.

Input

The first line of the input contains integers n and k (1 ≤ n, k ≤ 5·105) — the number of videos and servers, respectively.

Next n lines contain the descriptions of the videos as pairs of integers si, mi (1 ≤ si, mi ≤ 109), where si is the time in seconds when the i-th video appeared and mi is its duration in minutes. It is guaranteed that all the si's are distinct and the videos are given in the chronological order of upload, that is in the order of increasing si.

Output

Print n numbers e1, e2, ..., en, where ei is the time in seconds after the servers start working, when the i-th video will be recompressed.

Examples

Input

3 2
1 5
2 5
3 5


Output

6
7
11


Input

6 1
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
6 3


Output

1000000001
2000000001
3000000001
4000000001
5000000001
5000000004

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Timofey has a big tree — an undirected connected graph with n vertices and no simple cycles. He likes to walk along it. His tree is flat so when he walks along it he sees it entirely. Quite naturally, when he stands on a vertex, he sees the tree as a rooted tree with the root in this vertex.

Timofey assumes that the more non-isomorphic subtrees are there in the tree, the more beautiful the tree is. A subtree of a vertex is a subgraph containing this vertex and all its descendants. You should tell Timofey the vertex in which he should stand to see the most beautiful rooted tree.

Subtrees of vertices u and v are isomorphic if the number of children of u equals the number of children of v, and their children can be arranged in such a way that the subtree of the first son of u is isomorphic to the subtree of the first son of v, the subtree of the second son of u is isomorphic to the subtree of the second son of v, and so on. In particular, subtrees consisting of single vertex are isomorphic to each other.

Input

First line contains single integer n (1 ≤ n ≤ 105) — number of vertices in the tree.

Each of the next n - 1 lines contains two integers ui and vi (1 ≤ ui, vi ≤ 105, ui ≠ vi), denoting the vertices the i-th edge connects.

It is guaranteed that the given graph is a tree.

Output

Print single integer — the index of the vertex in which Timofey should stand. If there are many answers, you can print any of them.

Examples

Input

3
1 2
2 3


Output

1


Input

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


Output

1


Input

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


Output

2

Note

In the first example we can stand in the vertex 1 or in the vertex 3 so that every subtree is non-isomorphic. If we stand in the vertex 2, then subtrees of vertices 1 and 3 are isomorphic.

In the second example, if we stand in the vertex 1, then only subtrees of vertices 4 and 5 are isomorphic.

In the third example, if we stand in the vertex 1, then subtrees of vertices 2, 3, 4, 6, 7 and 8 are isomorphic. If we stand in the vertex 2, than only subtrees of vertices 3, 4, 6, 7 and 8 are isomorphic. If we stand in the vertex 5, then subtrees of vertices 2, 3, 4, 6, 7 and 8 are isomorphic, and subtrees of vertices 1 and 9 are isomorphic as well: 
    
    
      
      1     9  
     /\    /\  
    7  8  4  2  
    

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a game that involves three variables, denoted A, B, and C.
As the game progresses, there will be N events where you are asked to make a choice.
Each of these choices is represented by a string s_i. If s_i is AB, you must add 1 to A or B then subtract 1 from the other; if s_i is AC, you must add 1 to A or C then subtract 1 from the other; if s_i is BC, you must add 1 to B or C then subtract 1 from the other.
After each choice, none of A, B, and C should be negative.
Determine whether it is possible to make N choices under this condition. If it is possible, also give one such way to make the choices.

-----Constraints-----
 - 1 \leq N \leq 10^5
 - 0 \leq A,B,C \leq 10^9
 - N, A, B, C are integers.
 - s_i is AB, AC, or BC.

-----Input-----
Input is given from Standard Input in the following format:
N A B C
s_1
s_2
:
s_N

-----Output-----
If it is possible to make N choices under the condition, print Yes; otherwise, print No.
Also, in the former case, show one such way to make the choices in the subsequent N lines. The (i+1)-th line should contain the name of the variable (A, B, or C) to which you add 1 in the i-th choice.

-----Sample Input-----
2 1 3 0
AB
AC

-----Sample Output-----
Yes
A
C

You can successfully make two choices, as follows:
 - In the first choice, add 1 to A and subtract 1 from B. A becomes 2, and B becomes 2.
 - In the second choice, add 1 to C and subtract 1 from A. C becomes 1, and A becomes 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A coordinate line has n segments, the i-th segment starts at the position l_{i} and ends at the position r_{i}. We will denote such a segment as [l_{i}, r_{i}].

You have suggested that one of the defined segments covers all others. In other words, there is such segment in the given set, which contains all other ones. Now you want to test your assumption. Find in the given set the segment which covers all other segments, and print its number. If such a segment doesn't exist, print -1.

Formally we will assume that segment [a, b] covers segment [c, d], if they meet this condition a ≤ c ≤ d ≤ b. 


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of segments. Next n lines contain the descriptions of the segments. The i-th line contains two space-separated integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ 10^9) — the borders of the i-th segment.

It is guaranteed that no two segments coincide.


-----Output-----

Print a single integer — the number of the segment that covers all other segments in the set. If there's no solution, print -1.

The segments are numbered starting from 1 in the order in which they appear in the input.


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

Output
-1

Input
6
1 5
2 3
1 10
7 10
7 7
10 10

Output
3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There is a board with a grid consisting of *n* rows and *m* columns, the rows are numbered from 1 from top to bottom and the columns are numbered from 1 from left to right. In this grid we will denote the cell that lies on row number *i* and column number *j* as (*i*,<=*j*).

A group of six numbers (*a*,<=*b*,<=*c*,<=*d*,<=*x*0,<=*y*0), where 0<=≤<=*a*,<=*b*,<=*c*,<=*d*, is a cross, and there is a set of cells that are assigned to it. Cell (*x*,<=*y*) belongs to this set if at least one of two conditions are fulfilled:
 -  |*x*0<=-<=*x*|<=≤<=*a* and |*y*0<=-<=*y*|<=≤<=*b* -  |*x*0<=-<=*x*|<=≤<=*c* and |*y*0<=-<=*y*|<=≤<=*d* 
Your task is to find the number of different groups of six numbers, (*a*,<=*b*,<=*c*,<=*d*,<=*x*0,<=*y*0) that determine the crosses of an area equal to *s*, which are placed entirely on the grid. The cross is placed entirely on the grid, if any of its cells is in the range of the grid (that is for each cell (*x*,<=*y*) of the cross 1<=≤<=*x*<=≤<=*n*; 1<=≤<=*y*<=≤<=*m* holds). The area of the cross is the number of cells it has.

Note that two crosses are considered distinct if the ordered groups of six numbers that denote them are distinct, even if these crosses coincide as sets of points.

Input Specification:
The input consists of a single line containing three integers *n*, *m* and *s* (1<=≤<=*n*,<=*m*<=≤<=500, 1<=≤<=*s*<=≤<=*n*·*m*). The integers are separated by a space.

Output Specification:
Print a single integer — the number of distinct groups of six integers that denote crosses with area *s* and that are fully placed on the *n*<=×<=*m* grid.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

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

Note:
In the first sample the sought groups of six numbers are: (0, 0, 0, 0, 1, 1), (0, 0, 0, 0, 1, 2), (0, 0, 0, 0, 2, 1), (0, 0, 0, 0, 2, 2).

In the second sample the sought groups of six numbers are: (0, 1, 1, 0, 2, 2), (0, 1, 1, 0, 2, 3), (1, 0, 0, 1, 2, 2), (1, 0, 0, 1, 2, 3).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sentence that consists of some words separated by a single space, and a searchWord.
You have to check if searchWord is a prefix of any word in sentence.
Return the index of the word in sentence where searchWord is a prefix of this word (1-indexed).
If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.
A prefix of a string S is any leading contiguous substring of S.
 
Example 1:
Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.

Example 2:
Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.

Example 3:
Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.

Example 4:
Input: sentence = "i use triple pillow", searchWord = "pill"
Output: 4

Example 5:
Input: sentence = "hello from the other side", searchWord = "they"
Output: -1

 
Constraints:

1 <= sentence.length <= 100
1 <= searchWord.length <= 10
sentence consists of lowercase English letters and spaces.
searchWord consists of lowercase English letters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kuro has just learned about permutations and he is really excited to create a new permutation type. He has chosen n distinct positive integers and put all of them in a set S. Now he defines a magical permutation to be:

  * A permutation of integers from 0 to 2^x - 1, where x is a non-negative integer. 
  * The [bitwise xor](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of any two consecutive elements in the permutation is an element in S.



Since Kuro is really excited about magical permutations, he wants to create the longest magical permutation possible. In other words, he wants to find the largest non-negative integer x such that there is a magical permutation of integers from 0 to 2^x - 1. Since he is a newbie in the subject, he wants you to help him find this value of x and also the magical permutation for that x.

Input

The first line contains the integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of elements in the set S.

The next line contains n distinct integers S_1, S_2, …, S_n (1 ≤ S_i ≤ 2 ⋅ 10^5) — the elements in the set S.

Output

In the first line print the largest non-negative integer x, such that there is a magical permutation of integers from 0 to 2^x - 1.

Then print 2^x integers describing a magical permutation of integers from 0 to 2^x - 1. If there are multiple such magical permutations, print any of them.

Examples

Input


3
1 2 3


Output


2
0 1 3 2 

Input


2
2 3


Output


2
0 2 1 3 

Input


4
1 2 3 4


Output


3
0 1 3 2 6 7 5 4 

Input


2
2 4


Output


0
0 

Input


1
20


Output


0
0 

Input


1
1


Output


1
0 1 

Note

In the first example, 0, 1, 3, 2 is a magical permutation since:

  * 0 ⊕ 1 = 1 ∈ S 
  * 1 ⊕ 3 = 2 ∈ S 
  * 3 ⊕ 2 = 1 ∈ S



Where ⊕ denotes [bitwise xor](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) operation.

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