vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given two strings, s1 and s2, composed of only English alphabets (both upper and lower cases), find the alphabets that occur in both the strings. find the common alphabets (if any).
Note:
1. Upper and lower alphabets are different.
2. Don't print any duplicates, even if they exit multiple times.
 
Example 1:
Input: s1 = "tUvGH", s2 = "Hhev"
Output: Hv
Explanation: The common letter are H and v. 
Hence output is, "Hv".
Example 2:
Input: s1 = "aabb", s2 = "ccll"
Output: nil
Explanation: There is nothing common, hence
the output is "nil".
 
Your Task:
You don't need to read or print anything. Your task is to complete the function commom_String() which takes s1 and s2 as input parameter and returns the letters which are common in both the strings in string format. If there is nothing common then returns "nil". The string which is returned must contain all the capital letters followed by small letter in ascending order.
 
Expected Time Complexity:  O(max(|s1|, |s2|)
Expected Space Complexity: O(k) where k is constant.
 
Constraints:
1 ≤ |s1|, |s2| ≤ 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A magic island Geraldion, where Gerald lives, has its own currency system. It uses banknotes of several values. But the problem is, the system is not perfect and sometimes it happens that Geraldionians cannot express a certain sum of money with any set of banknotes. Of course, they can use any number of banknotes of each value. Such sum is called unfortunate. Gerald wondered: what is the minimum unfortunate sum?


-----Input-----

The first line contains number n (1 ≤ n ≤ 1000) — the number of values of the banknotes that used in Geraldion. 

The second line contains n distinct space-separated numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^6) — the values of the banknotes.


-----Output-----

Print a single line — the minimum unfortunate sum. If there are no unfortunate sums, print  - 1.


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

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan is fond of genealogy. Currently he is studying a particular genealogical structure, which consists of some people. In this structure every person has either both parents specified, or none. Additionally, each person has exactly one child, except for one special person, who does not have any children. The people in this structure are conveniently numbered from 1 to n, and s_i denotes the child of the person i (and s_i = 0 for exactly one person who does not have any children).

We say that a is an ancestor of b if either a = b, or a has a child, who is an ancestor of b. That is a is an ancestor for a, s_a, s_{s_a}, etc.

We say that person i is imbalanced in case this person has both parents specified, and the total number of ancestors of one of the parents is at least double the other. 

Ivan counted the number of imbalanced people in the structure, and got k people in total. However, he is not sure whether he computed it correctly, and would like to check if there is at least one construction with n people that have k imbalanced people in total. Please help him to find one such construction, or determine if it does not exist.

Input

The input contains two integers n and k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n), the total number of people and the number of imbalanced people.

Output

If there are no constructions with n people and k imbalanced people, output NO.

Otherwise output YES on the first line, and then n integers s_1, s_2, …, s_n (0 ≤ s_i ≤ n), which describes the construction and specify the child of each node (or 0, if the person does not have any children).

Examples

Input


3 0


Output


YES
0 1 1


Input


5 1


Output


YES
0 1 1 3 3


Input


3 2


Output


NO

Note

In the first example case one can have a construction with 3 people, where 1 person has 2 parents.

In the second example case one can use the following construction: 

<image>

Only person 1 is imbalanced, because one of their parents has 1 ancestor in total, and the other parent has 3 ancestors.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Simon has an array a_1, a_2, ..., a_{n}, consisting of n positive integers. Today Simon asked you to find a pair of integers l, r (1 ≤ l ≤ r ≤ n), such that the following conditions hold:  there is integer j (l ≤ j ≤ r), such that all integers a_{l}, a_{l} + 1, ..., a_{r} are divisible by a_{j};  value r - l takes the maximum value among all pairs for which condition 1 is true; 

Help Simon, find the required pair of numbers (l, r). If there are multiple required pairs find all of them.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 3·10^5).

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^6).


-----Output-----

Print two integers in the first line — the number of required pairs and the maximum value of r - l. On the following line print all l values from optimal pairs in increasing order.


-----Examples-----
Input
5
4 6 9 3 6

Output
1 3
2 

Input
5
1 3 5 7 9

Output
1 4
1 

Input
5
2 3 5 7 11

Output
5 0
1 2 3 4 5 



-----Note-----

In the first sample the pair of numbers is right, as numbers 6, 9, 3 are divisible by 3.

In the second sample all numbers are divisible by number 1.

In the third sample all numbers are prime, so conditions 1 and 2 are true only for pairs of numbers (1, 1), (2, 2), (3, 3), (4, 4), (5, 5).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are playing a game on a $n \times m$ grid, in which the computer has selected some cell $(x, y)$ of the grid, and you have to determine which one.

To do so, you will choose some $k$ and some $k$ cells $(x_1, y_1),\, (x_2, y_2), \ldots, (x_k, y_k)$, and give them to the computer. In response, you will get $k$ numbers $b_1,\, b_2, \ldots b_k$, where $b_i$ is the manhattan distance from $(x_i, y_i)$ to the hidden cell $(x, y)$ (so you know which distance corresponds to which of $k$ input cells).

After receiving these $b_1,\, b_2, \ldots, b_k$, you have to be able to determine the hidden cell. What is the smallest $k$ for which is it possible to always guess the hidden cell correctly, no matter what cell computer chooses?

As a reminder, the manhattan distance between cells $(a_1, b_1)$ and $(a_2, b_2)$ is equal to $|a_1-a_2|+|b_1-b_2|$.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.

The single line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 10^9$) — the number of rows and the number of columns in the grid.


-----Output-----

For each test case print a single integer — the minimum $k$ for that test case.


-----Examples-----

Input
2
2 3
3 1
Output
2
1


-----Note-----

In the first test case, the smallest such $k$ is $2$, for which you can choose, for example, cells $(1, 1)$ and $(2, 1)$.

Note that you can't choose cells $(1, 1)$ and $(2, 3)$ for $k = 2$, as both cells $(1, 2)$ and $(2, 1)$ would give $b_1 = 1, b_2 = 2$, so we wouldn't be able to determine which cell is hidden if computer selects one of those.

In the second test case, you should choose $k = 1$, for it you can choose cell $(3, 1)$ or $(1, 1)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arcady is a copywriter. His today's task is to type up an already well-designed story using his favorite text editor.

Arcady types words, punctuation signs and spaces one after another. Each letter and each sign (including line feed) requires one keyboard click in order to be printed. Moreover, when Arcady has a non-empty prefix of some word on the screen, the editor proposes a possible autocompletion for this word, more precisely one of the already printed words such that its prefix matches the currently printed prefix if this word is unique. For example, if Arcady has already printed «codeforces», «coding» and «codeforces» once again, then there will be no autocompletion attempt for «cod», but if he proceeds with «code», the editor will propose «codeforces».

With a single click Arcady can follow the editor's proposal, i.e. to transform the current prefix to it. Note that no additional symbols are printed after the autocompletion (no spaces, line feeds, etc). What is the minimum number of keyboard clicks Arcady has to perform to print the entire text, if he is not allowed to move the cursor or erase the already printed symbols?

A word here is a contiguous sequence of latin letters bordered by spaces, punctuation signs and line/text beginnings/ends. Arcady uses only lowercase letters. For example, there are 20 words in «it's well-known that tic-tac-toe is a paper-and-pencil game for two players, x and o.».


-----Input-----

The only line contains Arcady's text, consisting only of lowercase latin letters, spaces, line feeds and the following punctuation signs: «.», «,», «?», «!», «'» and «-». The total amount of symbols doesn't exceed 3·10^5. It's guaranteed that all lines are non-empty.


-----Output-----

Print a single integer — the minimum number of clicks.


-----Examples-----
Input
snow affects sports such as skiing, snowboarding, and snowmachine travel.
snowboarding is a recreational activity and olympic and paralympic sport.

Output
141

Input
'co-co-co, codeforces?!'

Output
25

Input
thun-thun-thunder, thunder, thunder
thunder, thun-, thunder
thun-thun-thunder, thunder
thunder, feel the thunder
lightning then the thunder
thunder, feel the thunder
lightning then the thunder
thunder, thunder

Output
183



-----Note-----

In sample case one it's optimal to use autocompletion for the first instance of «snowboarding» after typing up «sn» and for the second instance of «snowboarding» after typing up «snowb». This will save 7 clicks.

In sample case two it doesn't matter whether to use autocompletion or not.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Igor the analyst has adopted n little bunnies. As we all know, bunnies love carrots. Thus, Igor has bought a carrot to be shared between his bunnies. Igor wants to treat all the bunnies equally, and thus he wants to cut the carrot into n pieces of equal area. 

Formally, the carrot can be viewed as an isosceles triangle with base length equal to 1 and height equal to h. Igor wants to make n - 1 cuts parallel to the base to cut the carrot into n pieces. He wants to make sure that all n pieces have the same area. Can you help Igor determine where to cut the carrot so that each piece have equal area?

 [Image] Illustration to the first example. 


-----Input-----

The first and only line of input contains two space-separated integers, n and h (2 ≤ n ≤ 1000, 1 ≤ h ≤ 10^5).


-----Output-----

The output should contain n - 1 real numbers x_1, x_2, ..., x_{n} - 1. The number x_{i} denotes that the i-th cut must be made x_{i} units away from the apex of the carrot. In addition, 0 < x_1 < x_2 < ... < x_{n} - 1 < h must hold. 

Your output will be considered correct if absolute or relative error of every number in your output doesn't exceed 10^{ - 6}.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


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

Output
1.154700538379 1.632993161855

Input
2 100000

Output
70710.678118654752



-----Note-----

Definition of isosceles triangle: https://en.wikipedia.org/wiki/Isosceles_triangle.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Greg has a pad. The pad's screen is an n × m rectangle, each cell can be either black or white. We'll consider the pad rows to be numbered with integers from 1 to n from top to bottom. Similarly, the pad's columns are numbered with integers from 1 to m from left to right.

Greg thinks that the pad's screen displays a cave if the following conditions hold:

  * There is a segment [l, r] (1 ≤ l ≤ r ≤ n), such that each of the rows l, l + 1, ..., r has exactly two black cells and all other rows have only white cells. 
  * There is a row number t (l ≤ t ≤ r), such that for all pairs of rows with numbers i and j (l ≤ i ≤ j ≤ t) the set of columns between the black cells in row i (with the columns where is these black cells) is the subset of the set of columns between the black cells in row j (with the columns where is these black cells). Similarly, for all pairs of rows with numbers i and j (t ≤ i ≤ j ≤ r) the set of columns between the black cells in row j (with the columns where is these black cells) is the subset of the set of columns between the black cells in row i (with the columns where is these black cells). 



Greg wondered, how many ways there are to paint a cave on his pad. Two ways can be considered distinct if there is a cell that has distinct colors on the two pictures.

Help Greg.

Input

The first line contains two integers n, m — the pad's screen size (1 ≤ n, m ≤ 2000).

Output

In the single line print the remainder after dividing the answer to the problem by 1000000007 (109 + 7).

Examples

Input

1 1


Output

0


Input

4 4


Output

485


Input

3 5


Output

451

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two numbers: 'left' and 'right' (1 <= 'left' <= 'right' <= 200000000000000)
return sum of all '1' occurencies in binary representations of numbers between 'left' and 'right' (including both)

``` 
Example:
countOnes 4 7 should return 8, because:
4(dec) = 100(bin), which adds 1 to the result.
5(dec) = 101(bin), which adds 2 to the result.
6(dec) = 110(bin), which adds 2 to the result.
7(dec) = 111(bin), which adds 3 to the result.
So finally result equals 8.
```
WARNING: Segment may contain billion elements, to pass this kata, your solution cannot iterate through all numbers in the segment!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's denote as $\text{popcount}(x)$ the number of bits set ('1' bits) in the binary representation of the non-negative integer x.

You are given multiple queries consisting of pairs of integers l and r. For each query, find the x, such that l ≤ x ≤ r, and $\text{popcount}(x)$ is maximum possible. If there are multiple such numbers find the smallest of them.


-----Input-----

The first line contains integer n — the number of queries (1 ≤ n ≤ 10000).

Each of the following n lines contain two integers l_{i}, r_{i} — the arguments for the corresponding query (0 ≤ l_{i} ≤ r_{i} ≤ 10^18).


-----Output-----

For each query print the answer in a separate line.


-----Examples-----
Input
3
1 2
2 4
1 10

Output
1
3
7



-----Note-----

The binary representations of numbers from 1 to 10 are listed below:

1_10 = 1_2

2_10 = 10_2

3_10 = 11_2

4_10 = 100_2

5_10 = 101_2

6_10 = 110_2

7_10 = 111_2

8_10 = 1000_2

9_10 = 1001_2

10_10 = 1010_2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nastya likes reading and even spends whole days in a library sometimes. Today she found a chronicle of Byteland in the library, and it stated that there lived shamans long time ago. It is known that at every moment there was exactly one shaman in Byteland, and there were n shamans in total enumerated with integers from 1 to n in the order they lived. Also, each shaman had a magic power which can now be expressed as an integer.

The chronicle includes a list of powers of the n shamans. Also, some shamans can be king-shamans, if they gathered all the power of their predecessors, i.e. their power is exactly the sum of powers of all previous shamans. Nastya is interested in whether there was at least one king-shaman in Byteland.

Unfortunately many of the powers are unreadable in the list, so Nastya is doing the following:

  * Initially she supposes some power for each shaman. 
  * After that she changes the power of some shaman q times (the shamans can differ) and after that wants to check if there is at least one king-shaman in the list. If yes, she wants to know the index of any king-shaman. 



Unfortunately the list is too large and Nastya wants you to help her.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 2·105).

The second line contains n integers a1, ..., an (0 ≤ ai ≤ 109), where ai is the magic power of the i-th shaman.

After that q lines follow, the i-th of them contains two integers pi and xi (1 ≤ pi ≤ n, 0 ≤ xi ≤ 109) that mean that the new power of the pi-th shaman is xi.

Output

Print q lines, the i-th of them should contain  - 1, if after the i-th change there are no shaman-kings, and otherwise a single integer j, where j is an index of some king-shaman after the i-th change.

If there are multiple king-shamans after each change, print the index of any of them.

Examples

Input

2 1
1 3
1 2


Output

-1


Input

3 4
2 2 3
1 1
1 2
2 4
3 6


Output

3
2
-1
3


Input

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


Output

1
-1
9
-1
4
-1
1

Note

In the first example powers of shamans after the first change are equal to (2, 3). The answer equals  - 1, because the sum of powers of shamans before the first shaman is equal to 0, and before the second is equal to 2.

In the second example after the first change the powers are equal to (1, 2, 3). The answer is equal to 3, because the power of the third shaman is equal to 3, and the sum of powers of the first and the second shaman is also 1 + 2 = 3. After the second change the powers become equal to (2, 2, 3), where the answer equals 2. After the third change the powers become equal to (2, 4, 3), where the answer equals  - 1. After the fourth change the powers become equal to (2, 4, 6), where the answer equals 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pritam is a priest in his village. He needs to pay his respects to k shrines which his all ancestors have visited and had asked their successors to pay the respect. But he hates walking so he wants to minimize the distance he has to travel to pay his respects. As he is busy packing he asks you to help him. He has acquired a bunch of portal scrolls through which he can create portal networks. Portals can only be created at shrines , and after entering a portal a he can exit at any desired portal. You have to give the minimum distance Pritam has to travel. There are number of cities which don’t have shrines but that can be traveled through.
You will be given n the number of cities and out of which first k cities have shrines. There is road connecting two cities which will be defined by three integers a, b and c where a and b are the cities and c is the distance between the cities. You have to calculate the minimum distance that need to be walked for this pilgrimage given that there is no restriction on number of portals that can be created but need to be created at shrines. After you have told him the distance he’ll decide whether it’s worth undertaking or not. You can assume that he starts from 1st city.
[Input]
First line contains integer t denoting number of test cases.
First line of every test case consists of 3 integers n, m and k denoting number of cities, number of roads and number of shrines respectively.
Next m lines of test case consists of 3 space separated integers a, b and c, where a and b are cities and c is the distance between them.
[Output]
For each test case print a single integer containing the minimum distance he need to walk for the pilgrimage.
[Constraints]
1 ≤ t ≤ 20
1 ≤ n ≤ 100
n-1 ≤ m ≤ (n*(n-1))/2
1 ≤ k ≤ n
1 ≤ a,b ≤ n
1 ≤ c ≤ 1000000

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

SAMPLE OUTPUT
14

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In some country live wizards. They love to ride trolleybuses.

A city in this country has a trolleybus depot with n trolleybuses. Every day the trolleybuses leave the depot, one by one and go to the final station. The final station is at a distance of d meters from the depot. We know for the i-th trolleybus that it leaves at the moment of time ti seconds, can go at a speed of no greater than vi meters per second, and accelerate with an acceleration no greater than a meters per second squared. A trolleybus can decelerate as quickly as you want (magic!). It can change its acceleration as fast as you want, as well. Note that the maximum acceleration is the same for all trolleys.

Despite the magic the trolleys are still powered by an electric circuit and cannot overtake each other (the wires are to blame, of course). If a trolleybus catches up with another one, they go together one right after the other until they arrive at the final station. Also, the drivers are driving so as to arrive at the final station as quickly as possible.

You, as head of the trolleybuses' fans' club, are to determine for each trolley the minimum time by which it can reach the final station. At the time of arrival at the destination station the trolleybus does not necessarily have zero speed. When a trolley is leaving the depot, its speed is considered equal to zero. From the point of view of physics, the trolleybuses can be considered as material points, and also we should ignore the impact on the speed of a trolley bus by everything, except for the acceleration and deceleration provided by the engine.

Input

The first input line contains three space-separated integers n, a, d (1 ≤ n ≤ 105, 1 ≤ a, d ≤ 106) — the number of trolleybuses, their maximum acceleration and the distance from the depot to the final station, correspondingly.

Next n lines contain pairs of integers ti vi (0 ≤ t1 < t2... < tn - 1 < tn ≤ 106, 1 ≤ vi ≤ 106) — the time when the i-th trolleybus leaves the depot and its maximum speed, correspondingly. The numbers in the lines are separated by spaces.

Output

For each trolleybus print a single line the time it arrives to the final station. Print the times for the trolleybuses in the order in which the trolleybuses are given in the input. The answer will be accepted if the absolute or relative error doesn't exceed 10 - 4.

Examples

Input

3 10 10000
0 10
5 11
1000 1


Output

1000.5000000000
1000.5000000000
11000.0500000000


Input

1 2 26
28 29


Output

33.0990195136

Note

In the first sample the second trolleybus will catch up with the first one, that will happen at distance 510.5 meters from the depot. The trolleybuses will go the remaining 9489.5 meters together at speed 10 meters per second. As a result, both trolleybuses will arrive to the final station by the moment of time 1000.5 seconds. The third trolleybus will not catch up with them. It will arrive to the final station by the moment of time 11000.05 seconds.

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