vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A duck hunter is doing his favorite thing, hunting. He lives in a two dimensional world and is located at point (0, 0). As he doesn't like walking for his prey, he prefers to shoot only vertically up (because in this case, the ducks fall straight into his hands). The hunter doesn't reload the gun immediately — r or more seconds must pass between the shots. When the hunter shoots up, the bullet immediately hits all the ducks who are directly above the hunter.

In a two dimensional world each duck is a horizontal segment that moves horizontally in the negative direction of the Ox axis at the speed 1 length unit per second. For each duck we know the values hi and ti — the x-coordinates of its head (the left end of the segment) and its tail (the right end of the segment) at time 0. The height where the duck is flying isn't important as the gun shoots vertically up to the infinite height and hits all the ducks on its way. 

<image> The figure to the first sample.

What maximum number of ducks can the hunter shoot? The duck is considered shot by the hunter if at the moment of the shot at least one of its point intersects the Oy axis. After the hunter shoots the duck, it falls and it can't be shot anymore. The hunter cannot make shots before the moment of time 0.

Input

The first line of the input contains integers n, r (1 ≤ n ≤ 200 000, 1 ≤ r ≤ 109) — the number of ducks and the minimum time in seconds between the shots. 

Then n lines follow, each of them contains two integers hi, ti ( - 109 ≤ hi < ti ≤ 109) — the x-coordinate of the head and tail of the i-th duck at the moment 0.

Output

Print a single integer — the maximum number of ducks that can be shot by the hunter.

Examples

Input

3 3
-3 0
1 3
-1 2


Output

3


Input

4 5
-1 1
2 4
5 9
6 8


Output

3

Note

In the first sample the hunter must shoot at time 0, this shot kills ducks 1 and 3. Then the hunter needs to reload the gun and shoot again at time 3. His second shot hits the tail of duck 2.

In the second sample the hunter can make shots at times 0 and 6 to hit three ducks.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string s, consisting of brackets of two types: '(', ')', '[' and ']'.

A string is called a regular bracket sequence (RBS) if it's of one of the following types: 

  * empty string; 
  * '(' + RBS + ')'; 
  * '[' + RBS + ']'; 
  * RBS + RBS. 



where plus is a concatenation of two strings.

In one move you can choose a non-empty subsequence of the string s (not necessarily consecutive) that is an RBS, remove it from the string and concatenate the remaining parts without changing the order.

What is the maximum number of moves you can perform?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of testcases.

Each of the next t lines contains a non-empty string, consisting only of characters '(', ')', '[' and ']'. The total length of the strings over all testcases doesn't exceed 2 ⋅ 10^5.

Output

For each testcase print a single integer — the maximum number of moves you can perform on a given string s.

Example

Input


5
()
[]()
([)]
)]([
)[(]


Output


1
2
2
0
1

Note

In the first example you can just erase the whole string.

In the second example you can first erase the brackets on positions 1 and 2: "[]()", then "()" is left. After that you can erase it whole. You could erase the whole string from the beginning but you would get one move instead of two.

In the third example you can first erase the brackets on positions 1 and 3: "([)]". They form an RBS "()". Then "[]" is left, so you can erase it whole.

In the fourth example there is no subsequence that is an RBS, so you can't perform a move at all.

In the fifth example you can erase the brackets on positions 2 and 4: ")[(]" and get ")(" as a result. You can erase nothing from it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once n people simultaneously signed in to the reception at the recently opened, but already thoroughly bureaucratic organization (abbreviated TBO). As the organization is thoroughly bureaucratic, it can accept and cater for exactly one person per day. As a consequence, each of n people made an appointment on one of the next n days, and no two persons have an appointment on the same day.

However, the organization workers are very irresponsible about their job, so none of the signed in people was told the exact date of the appointment. The only way to know when people should come is to write some requests to TBO.

The request form consists of m empty lines. Into each of these lines the name of a signed in person can be written (it can be left blank as well). Writing a person's name in the same form twice is forbidden, such requests are ignored. TBO responds very quickly to written requests, but the reply format is of very poor quality — that is, the response contains the correct appointment dates for all people from the request form, but the dates are in completely random order. Responds to all requests arrive simultaneously at the end of the day (each response specifies the request that it answers).

Fortunately, you aren't among these n lucky guys. As an observer, you have the following task — given n and m, determine the minimum number of requests to submit to TBO to clearly determine the appointment date for each person.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. Each of the following t lines contains two integers n and m (1 ≤ n, m ≤ 109) — the number of people who have got an appointment at TBO and the number of empty lines in the request form, correspondingly.

Output

Print t lines, each containing an answer for the corresponding test case (in the order they are given in the input) — the minimum number of requests to submit to TBO.

Examples

Input

5
4 1
4 2
7 3
1 1
42 7


Output

3
2
3
0
11

Note

In the first sample, you need to submit three requests to TBO with three different names. When you learn the appointment dates of three people out of four, you can find out the fourth person's date by elimination, so you do not need a fourth request.

In the second sample you need only two requests. Let's number the persons from 1 to 4 and mention persons 1 and 2 in the first request and persons 1 and 3 in the second request. It is easy to see that after that we can clearly determine each person's appointment date regardless of the answers obtained from TBO.

In the fourth sample only one person signed up for an appointment. He doesn't need to submit any requests — his appointment date is tomorrow.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mashmokh works in a factory. At the end of each day he must turn off all of the lights. 

The lights on the factory are indexed from 1 to n. There are n buttons in Mashmokh's room indexed from 1 to n as well. If Mashmokh pushes button with index i, then each light with index not less than i that is still turned on turns off.

Mashmokh is not very clever. So instead of pushing the first button he pushes some of the buttons randomly each night. He pushed m distinct buttons b_1, b_2, ..., b_{m} (the buttons were pushed consecutively in the given order) this night. Now he wants to know for each light the index of the button that turned this light off. Please note that the index of button b_{i} is actually b_{i}, not i.

Please, help Mashmokh, print these indices.


-----Input-----

The first line of the input contains two space-separated integers n and m (1 ≤ n, m ≤ 100), the number of the factory lights and the pushed buttons respectively. The next line contains m distinct space-separated integers b_1, b_2, ..., b_{m} (1 ≤ b_{i} ≤ n).

It is guaranteed that all lights will be turned off after pushing all buttons.


-----Output-----

Output n space-separated integers where the i-th number is index of the button that turns the i-th light off.


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

Output
1 1 3 4 4 

Input
5 5
5 4 3 2 1

Output
1 2 3 4 5 



-----Note-----

In the first sample, after pressing button number 4, lights 4 and 5 are turned off and lights 1, 2 and 3 are still on. Then after pressing button number 3, light number 3 is turned off as well. Pressing button number 1 turns off lights number 1 and 2 as well so pressing button number 2 in the end has no effect. Thus button number 4 turned lights 4 and 5 off, button number 3 turned light 3 off and button number 1 turned light 1 and 2 off.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp likes to play with numbers. He takes some integer number $x$, writes it down on the board, and then performs with it $n - 1$ operations of the two kinds:   divide the number $x$ by $3$ ($x$ must be divisible by $3$);  multiply the number $x$ by $2$. 

After each operation, Polycarp writes down the result on the board and replaces $x$ by the result. So there will be $n$ numbers on the board after all.

You are given a sequence of length $n$ — the numbers that Polycarp wrote down. This sequence is given in arbitrary order, i.e. the order of the sequence can mismatch the order of the numbers written on the board.

Your problem is to rearrange (reorder) elements of this sequence in such a way that it can match possible Polycarp's game in the order of the numbers written on the board. I.e. each next number will be exactly two times of the previous number or exactly one third of previous number.

It is guaranteed that the answer exists.


-----Input-----

The first line of the input contatins an integer number $n$ ($2 \le n \le 100$) — the number of the elements in the sequence. The second line of the input contains $n$ integer numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 3 \cdot 10^{18}$) — rearranged (reordered) sequence that Polycarp can wrote down on the board.


-----Output-----

Print $n$ integer numbers — rearranged (reordered) input sequence that can be the sequence that Polycarp could write down on the board.

It is guaranteed that the answer exists.


-----Examples-----
Input
6
4 8 6 3 12 9

Output
9 3 6 12 4 8 

Input
4
42 28 84 126

Output
126 42 84 28 

Input
2
1000000000000000000 3000000000000000000

Output
3000000000000000000 1000000000000000000 



-----Note-----

In the first example the given sequence can be rearranged in the following way: $[9, 3, 6, 12, 4, 8]$. It can match possible Polycarp's game which started with $x = 9$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call a string a phone number if it has length 11 and fits the pattern "8xxxxxxxxxx", where each "x" is replaced by a digit.

For example, "80123456789" and "80000000000" are phone numbers, while "8012345678" and "79000000000" are not.

You have $n$ cards with digits, and you want to use them to make as many phone numbers as possible. Each card must be used in at most one phone number, and you don't have to use all cards. The phone numbers do not necessarily have to be distinct.


-----Input-----

The first line contains an integer $n$ — the number of cards with digits that you have ($1 \leq n \leq 100$).

The second line contains a string of $n$ digits (characters "0", "1", ..., "9") $s_1, s_2, \ldots, s_n$. The string will not contain any other characters, such as leading or trailing spaces.


-----Output-----

If at least one phone number can be made from these cards, output the maximum number of phone numbers that can be made. Otherwise, output 0.


-----Examples-----
Input
11
00000000008

Output
1

Input
22
0011223344556677889988

Output
2

Input
11
31415926535

Output
0



-----Note-----

In the first example, one phone number, "8000000000", can be made from these cards.

In the second example, you can make two phone numbers from the cards, for example, "80123456789" and "80123456789".

In the third example you can't make any phone number from the given cards.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers arr and two integers k and threshold.
Return the number of sub-arrays of size k and average greater than or equal to threshold.
 
Example 1:
Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).

Example 2:
Input: arr = [1,1,1,1,1], k = 1, threshold = 0
Output: 5

Example 3:
Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.

Example 4:
Input: arr = [7,7,7,7,7,7,7], k = 7, threshold = 7
Output: 1

Example 5:
Input: arr = [4,4,4,4], k = 4, threshold = 1
Output: 1

 
Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One Big Software Company has *n* employees numbered from 1 to *n*. The director is assigned number 1. Every employee of the company except the director has exactly one immediate superior. The director, of course, doesn't have a superior.

We will call person *a* a subordinates of another person *b*, if either *b* is an immediate supervisor of *a*, or the immediate supervisor of *a* is a subordinate to person *b*. In particular, subordinates of the head are all other employees of the company.

To solve achieve an Important Goal we need to form a workgroup. Every person has some efficiency, expressed by a positive integer *a**i*, where *i* is the person's number. The efficiency of the workgroup is defined as the total efficiency of all the people included in it.

The employees of the big software company are obsessed with modern ways of work process organization. Today pair programming is at the peak of popularity, so the workgroup should be formed with the following condition. Each person entering the workgroup should be able to sort all of his subordinates who are also in the workgroup into pairs. In other words, for each of the members of the workgroup the number of his subordinates within the workgroup should be even.

Your task is to determine the maximum possible efficiency of the workgroup formed at observing the given condition. Any person including the director of company can enter the workgroup.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=2·105) — the number of workers of the Big Software Company. 

Then *n* lines follow, describing the company employees. The *i*-th line contains two integers *p**i*,<=*a**i* (1<=≤<=*a**i*<=≤<=105) — the number of the person who is the *i*-th employee's immediate superior and *i*-th employee's efficiency. For the director *p*1<==<=<=-<=1, for all other people the condition 1<=≤<=*p**i*<=&lt;<=*i* is fulfilled.

Output Specification:
Print a single integer — the maximum possible efficiency of the workgroup.

Demo Input:
['7\n-1 3\n1 2\n1 1\n1 4\n4 5\n4 3\n5 2\n']

Demo Output:
['17\n']

Note:
In the sample test the most effective way is to make a workgroup from employees number 1, 2, 4, 5, 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Where do odds begin, and where do they end? Where does hope emerge, and will they ever break?

Given an integer sequence a_1, a_2, ..., a_{n} of length n. Decide whether it is possible to divide it into an odd number of non-empty subsegments, the each of which has an odd length and begins and ends with odd numbers.

A subsegment is a contiguous slice of the whole sequence. For example, {3, 4, 5} and {1} are subsegments of sequence {1, 2, 3, 4, 5, 6}, while {1, 2, 4} and {7} are not.


-----Input-----

The first line of input contains a non-negative integer n (1 ≤ n ≤ 100) — the length of the sequence.

The second line contains n space-separated non-negative integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 100) — the elements of the sequence.


-----Output-----

Output "Yes" if it's possible to fulfill the requirements, and "No" otherwise.

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


-----Examples-----
Input
3
1 3 5

Output
Yes

Input
5
1 0 1 5 1

Output
Yes

Input
3
4 3 1

Output
No

Input
4
3 9 9 3

Output
No



-----Note-----

In the first example, divide the sequence into 1 subsegment: {1, 3, 5} and the requirements will be met.

In the second example, divide the sequence into 3 subsegments: {1, 0, 1}, {5}, {1}.

In the third example, one of the subsegments must start with 4 which is an even number, thus the requirements cannot be met.

In the fourth example, the sequence can be divided into 2 subsegments: {3, 9, 9}, {3}, but this is not a valid solution because 2 is an even number.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the Bus of Characters there are $n$ rows of seat, each having $2$ seats. The width of both seats in the $i$-th row is $w_i$ centimeters. All integers $w_i$ are distinct.

Initially the bus is empty. On each of $2n$ stops one passenger enters the bus. There are two types of passengers:   an introvert always chooses a row where both seats are empty. Among these rows he chooses the one with the smallest seats width and takes one of the seats in it;  an extrovert always chooses a row where exactly one seat is occupied (by an introvert). Among these rows he chooses the one with the largest seats width and takes the vacant place in it. 

You are given the seats width in each row and the order the passengers enter the bus. Determine which row each passenger will take.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 200\,000$) — the number of rows in the bus.

The second line contains the sequence of integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^{9}$), where $w_i$ is the width of each of the seats in the $i$-th row. It is guaranteed that all $w_i$ are distinct.

The third line contains a string of length $2n$, consisting of digits '0' and '1' — the description of the order the passengers enter the bus. If the $j$-th character is '0', then the passenger that enters the bus on the $j$-th stop is an introvert. If the $j$-th character is '1', the the passenger that enters the bus on the $j$-th stop is an extrovert. It is guaranteed that the number of extroverts equals the number of introverts (i. e. both numbers equal $n$), and for each extrovert there always is a suitable row.


-----Output-----

Print $2n$ integers — the rows the passengers will take. The order of passengers should be the same as in input.


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

Output
2 1 1 2 

Input
6
10 8 9 11 13 5
010010011101

Output
6 6 2 3 3 1 4 4 1 2 5 5 



-----Note-----

In the first example the first passenger (introvert) chooses the row $2$, because it has the seats with smallest width. The second passenger (introvert) chooses the row $1$, because it is the only empty row now. The third passenger (extrovert) chooses the row $1$, because it has exactly one occupied seat and the seat width is the largest among such rows. The fourth passenger (extrovert) chooses the row $2$, because it is the only row with an empty place.

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

The kindergarten attached to the University of Aizu is a kindergarten where children who love programming gather. Yu, one of the kindergarten children, loves lowercase letters as much as programming. Yu-kun decided to write a scoring program for a new play that uses paper, circles, lines, and lowercase letters.

Problem

Initially, V circles and E lines are drawn on the paper. The circles are numbered from 0 in ascending order, with one lowercase letter or nothing in each circle. Each line connects two different circles. A circle cannot be connected by more than 26 lines.

The play procedure is as follows.

1. Select one circle with nothing written on it. If such a circle does not exist, this process ends.
2. Write one lowercase letter in the circle. However, if the circle is already connected to a circle with lowercase letters by a line, the same lowercase letters as the lowercase letters cannot be written.
3. Return to 1.



After writing lowercase letters in all the circles according to the above procedure, arrange the lowercase letters in the circles in ascending order of the circle numbers to make a character string. I want to minimize the character strings that can be created in this way in lexicographical order. There are two strings s and t of the same length, and s is smaller than t in lexicographical order in the following cases. si represents the i-th lowercase letter of the string s and ti represents the i-th lowercase letter of the string t. For the smallest i where si differs from ti, si is less than ti.

Since the initial state of the paper is given, output the smallest character string that can be created according to the above procedure in lexicographical order.

Constraints

The input satisfies the following conditions.

* 1 ≤ V ≤ 100,000
* 0 ≤ E ≤ 200,000
* ai is either lowercase or'?' (0 ≤ i ≤ V-1)
* 0 ≤ si, ti ≤ V-1 (si <ti, 0 ≤ i ≤ E-1)
* One circle cannot be connected by more than 26 lines

Input


V E
a0 a1 ... a (V-1)
s0 t0
s1 t1
...
s (E-1) t (E-1)


The number of circles V and the number of lines E are given on the first line, separated by blanks.

The initial state of the circle is given on the second line, separated by blanks.

If ai is a lowercase letter, the lowercase letter is written in the i-th circle, and if it is'?', It means that nothing is written in the i-th circle.

The line information is given as si ti on the following E line, which means that the si and ti circles are connected by a line.

Output

Output the smallest character string in the dictionary order on one line among the character strings that can be created according to the procedure in the question sentence.

Examples

Input

3 3
c ? ?
0 1
0 2
1 2


Output

cab


Input

3 2
c ? ?
0 1
0 2


Output

caa


Input

7 6
? a ? ? z a ?
0 1
0 2
3 4
4 5
4 6
5 6


Output

baaazab


Input

5 0
? ? ? ? ?


Output

aaaaa

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