vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Okabe and Super Hacker Daru are stacking and removing boxes. There are n boxes numbered from 1 to n. Initially there are no boxes on the stack.

Okabe, being a control freak, gives Daru 2n commands: n of which are to add a box to the top of the stack, and n of which are to remove a box from the top of the stack and throw it in the trash. Okabe wants Daru to throw away the boxes in the order from 1 to n. Of course, this means that it might be impossible for Daru to perform some of Okabe's remove commands, because the required box is not on the top of the stack.

That's why Daru can decide to wait until Okabe looks away and then reorder the boxes in the stack in any way he wants. He can do it at any point of time between Okabe's commands, but he can't add or remove boxes while he does it.

Tell Daru the minimum number of times he needs to reorder the boxes so that he can successfully complete all of Okabe's commands. It is guaranteed that every box is added before it is required to be removed.


-----Input-----

The first line of input contains the integer n (1 ≤ n ≤ 3·10^5) — the number of boxes.

Each of the next 2n lines of input starts with a string "add" or "remove". If the line starts with the "add", an integer x (1 ≤ x ≤ n) follows, indicating that Daru should add the box with number x to the top of the stack. 

It is guaranteed that exactly n lines contain "add" operations, all the boxes added are distinct, and n lines contain "remove" operations. It is also guaranteed that a box is always added before it is required to be removed.


-----Output-----

Print the minimum number of times Daru needs to reorder the boxes to successfully complete all of Okabe's commands.


-----Examples-----
Input
3
add 1
remove
add 2
add 3
remove
remove

Output
1

Input
7
add 3
add 2
add 1
remove
add 4
remove
remove
remove
add 6
add 7
add 5
remove
remove
remove

Output
2



-----Note-----

In the first sample, Daru should reorder the boxes after adding box 3 to the stack.

In the second sample, Daru should reorder the boxes after adding box 4 and box 7 to the stack.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Zurikela is creating a graph with a special graph maker. At the begining, it is empty and has no nodes or edges. He can perform $3$ types of operations:    

$\mbox{A}$ $\boldsymbol{x}$: Create a set of $\boldsymbol{x}$ new nodes and name it $\boldsymbol{set}$-$\mbox{K}$.    
$\mbox{B}$ $\boldsymbol{x}$ $y$: Create edges between nodes of $\boldsymbol{set}$-$\boldsymbol{x}$ and $\boldsymbol{set}$-$y$.      
$\mbox{C}$ $\boldsymbol{x}$: Create a set composed of nodes from $\boldsymbol{set}$-$\boldsymbol{x}$ and its directly and indirectly connected nodes, called $\boldsymbol{set}$-$\mbox{K}$. Note that each node can only exist in one set, so other sets become empty.     

The first $\boldsymbol{set}$'s name will be $\boldsymbol{set}$-$\mbox{1}$. In first and third operation $\mbox{K}$ is referring to the index of new set:

K = [index of last created set] + 1

Create the graph by completing the $\mbox{Q}$ operations specified during input. Then calculate the maximum number of independent nodes (i.e.:how many nodes in the final graph which don't have direct edge between them).

Input Format

The first line contains $\mbox{Q}$. 

The $\mbox{Q}$ subsequent lines each contain an operation to be performed.

Constraints 

$1\leq Q\leq10^5$.

For the first operation, $1\leq x\leq10^4$. 

For the second operation, $x<y$ and all $y$s are distinct.

For the second and third operation, it's guaranteed that $\boldsymbol{set}$-$\boldsymbol{x}$ and $\boldsymbol{set}$-$y$ exist.     

Output Format

Print maximum number of independent nodes in the final graph (i.e.: nodes which have no direct connection to one another).

Sample Input
8
A 1
A 2
B 1 2
C 1
A 2
A 3
B 3 4
B 4 5

Sample Output
5

Explanation

There are $8$ operations.

After first operation$\left({A\mbox{1}}\right)$:

After second operation$\left({A\mbox{2}}\right)$:

After third operation$(B\:1\:2)$:

After fourth operation$\left({C1}\right)$:

After fifth and sixth operation $\left({A\mbox{2}}\right)$ and $(A3)$:

After seventh operation$\left({B\:\:3\:\:4}\right)$:

After eigth operation$\left(B\:4\:5\right)$:

There are $2$ independent nodes in $\boldsymbol{set}$-$3$ and $3$ independent nodes in $\boldsymbol{set}$-$5$, so we print their sum ($5$) as our answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Firdavs is living on planet F. There are $N$ cities (numbered $1$ through $N$) on this planet; let's denote the value of city $i$ by $v_i$. Firdavs can travel directly from each city to any other city. When he travels directly from city $x$ to city $y$, he needs to pay $f(x, y) = |v_y-v_x|+y-x$ coins (this number can be negative, in which case he receives $-f(x, y)$ coins).
Let's define a simple path from city $x$ to city $y$ with length $k \ge 1$ as a sequence of cities $a_1, a_2, \ldots, a_k$ such that all cities in this sequence are different, $a_1 = x$ and $a_k = y$. The cost of such a path is $\sum_{i=1}^{k-1} f(a_i, a_{i+1})$.
You need to answer some queries for Firdavs. In each query, you are given two cities $x$ and $y$, and you need to find the minimum cost of a simple path from city $x$ to city $y$. Then, you need to find the length of the longest simple path from $x$ to $y$ with this cost.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $Q$.
- The second line contains $N$ space-separated integers $v_1, v_2, \ldots, v_N$.
- The following $Q$ lines describe queries. Each of these lines contains two space-separated integers $x$ and $y$.

-----Output-----
For each query, print a single line containing two space-separated integers ― the minimum cost and the maximum length.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N, Q \le 2 \cdot 10^5$
- $0 \le v_i \le 10^9$ for each valid $i$
- $1 \le x, y \le N$
- the sum of $N$ in all test cases does not exceed $5 \cdot 10^5$
- the sum of $Q$ in all test cases does not exceed $5 \cdot 10^5$

-----Subtasks-----
Subtask #1 (30 points):
- $1 \le N, Q \le 1,000$
- $v_1 < v_2 < \ldots < v_N$
- the sum of $N$ in all test cases does not exceed $5,000$
- the sum of $Q$ in all test cases does not exceed $5,000$
Subtask #2 (70 points): original constraints

-----Example Input-----
2
4 2
4 2 5 7
2 3
3 4
2 1
1 1
2 1

-----Example Output-----
4 3
3 2
-1 2

-----Explanation-----
Example case 1: For the first query, there are two paths with cost $4$ from city $2$ to city $3$:
- $2 \rightarrow 1 \rightarrow 3$: cost $(|4-2|+1-2)+(|5-4|+3-1) = 4$, length $3$
- $2 \rightarrow 3$: cost $|5-2|+3-2 = 4$, length $2$
All other paths have greater costs, so the minimum cost is $4$. Among these two paths, we want the one with greater length, which is $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a binary array A=(A_1,A_2,\cdots,A_N) of length N.

Process Q queries of the following types. The i-th query is represented by three integers T_i,L_i,R_i.

* T_i=1: Replace the value of A_j with 1-A_j for each L_i \leq j \leq R_i.
* T_i=2: Calculate the inversion(*) of the array A_{L_i},A_{L_i+1},\cdots,A_{R_i}．



Note：The inversion of the array x_1,x_2,\cdots,x_k is the number of the pair of integers i,j with 1 \leq i < j \leq k, x_i > x_j.

Constraints

* 1 \leq N \leq 2 \times 10^5
* 0 \leq A_i \leq 1
* 1 \leq Q \leq 2 \times 10^5
* 1 \leq T_i \leq 2
* 1 \leq L_i \leq R_i \leq N
* All values in Input are integer.

Input

Input is given from Standard Input in the following format:


N Q
A_1 A_2 \cdots A_N
T_1 L_1 R_1
T_2 L_2 R_2
\vdots
T_Q L_Q R_Q


Output

For each query with T_i=2, print the answer.

Example

Input

5 5
0 1 0 0 1
2 1 5
1 3 4
2 2 5
1 1 3
2 1 2


Output

2
0
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have an array A of size N containing only positive numbers. You have to output the maximum possible value of A[i]%A[j] where 1<=i,j<=N. 

-----Input-----
The first line of each test case contains a single integer N denoting the size of the array. The next N lines contains integers A1, A2, ..., AN denoting the numbers

-----Output-----
Output a single integer answering what is asked in the problem.

-----Subtask 1 (20 points)-----
- 1 ≤ N ≤ 5000
- 1 ≤ A[i] ≤ 2*(10^9)

-----Subtask 2 (80 points)-----
- 1 ≤ N ≤ 1000000
- 1 ≤ A[i] ≤ 2*(10^9)

-----Example-----
Input:
2
1
2

Output:
1

-----Explanation-----
There will be four values, A[0]%A[0] = 0, A[0]%A[1]=1, A[1]%A[0]=0, A[1]%A[1]=0, and hence the output will be the maximum among them all, that is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We will call a string x good if it satisfies the following condition:

* Condition: x can be represented as a concatenation of two copies of another string y of length at least 1.



For example, `aa` and `bubobubo` are good; an empty string, `a`, `abcabcabc` and `abba` are not good.

Eagle and Owl created a puzzle on good strings. Find one string s that satisfies the following conditions. It can be proved that such a string always exists under the constraints in this problem.

* 1 ≤ |s| ≤ 200
* Each character of s is one of the 100 characters represented by the integers 1 through 100.
* Among the 2^{|s|} subsequences of s, exactly N are good strings.

Constraints

* 1 ≤ N ≤ 10^{12}

Input

Input is given from Standard Input in the following format:


N


Output

In the first line, print |s|, the length of s. In the second line, print the elements in s in order, with spaces in between. Any string that satisfies the above conditions will be accepted.

Examples

Input

7


Output

4
1 1 1 1


Input

299


Output

23
32 11 11 73 45 8 11 83 83 8 45 32 32 10 100 73 32 83 45 73 32 11 10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A new bus route is opened in the city <image>. The route is a closed polygon line in the place, with all segments parallel to one of the axes. m buses will operate on the route. All buses move in a loop along the route in the same direction with equal constant velocities (stopping times are negligible in this problem).

Buses start their movement in the first vertex of the route with equal interval. Suppose that T is the total time for a single bus to travel the whole loop of the route. Then, the bus 1 starts moving at time 0, the bus 2 starts at time T / m, the bus 3 starts at time 2T / m, and so on; finally, the bus m starts moving at time (m - 1)T / m. Thus, all intervals between pairs of consecutive buses (including the interval between the last and the first bus) are equal.

Buses can communicate with each other via wireless transmitters of equal power. If the transmitters have power D, then only buses within distance D of each other can communicate.

The buses are also equipped with a distributed system of schedule tracking. For all buses to stick to the schedule, the system has to synchronize the necessary data between all buses from time to time. At the moment of synchronization, the bus 1 communicates with the bus 2, the bus 2 — with bus 3, and so on; also, the bus m communicates with the bus 1.

As a research employee, you are tasked with finding the smallest value of D such that it is possible to find a time moment to perform synchronization once all buses have started moving. 

Input

The first line contains two integers n and m (2 ≤ n, m ≤ 105) — the number of vertices of the polygonal line, and the number of buses respectively.

Next n lines describe the vertices of the route in the traversing order. Each of these lines contains two integers xi, yi ( - 1000 ≤ xi, yi ≤ 1000) — coordinates of respective vertex.

It is guaranteed that each leg of the route (including the leg between the last and the first vertex) is paralles to one of the coordinate axes. Moreover, no two subsequent vertices of the route coincide. The route is allowed to have self-intersections, and travel along the same segment multiple times.

Output

Print one real number — the answer to the problem. Your answer will be accepted if the relative or the absolute error doesn't exceed 10 - 6.

Examples

Input

4 2
0 0
0 1
1 1
1 0


Output

1.000000000


Input

2 2
0 0
1 0


Output

0.000000000

Note

Suppose that each bus travel 1 distance unit per second.

In the first sample case, in 0.5 seconds buses will be at distance 1, hence we can choose D = 1.

In the second sample case, in 0.5 seconds both buses will be at (0.5, 0), hence we can choose D = 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shubham has an array $a$ of size $n$, and wants to select exactly $x$ elements from it, such that their sum is odd. These elements do not have to be consecutive. The elements of the array are not guaranteed to be distinct.

Tell him whether he can do so.


-----Input-----

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

The first line of each test case contains two integers $n$ and $x$ $(1 \le x \le n \le 1000)$ — the length of the array and the number of elements you need to choose.

The next line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 1000)$ — elements of the array.


-----Output-----

For each test case, print "Yes" or "No" depending on whether it is possible to choose $x$ elements such that their sum is odd.

You may print every letter in any case you want.


-----Example-----
Input
5
1 1
999
1 1
1000
2 1
51 50
2 2
51 50
3 3
101 102 103

Output
Yes
No
Yes
Yes
No



-----Note-----

For $1$st case: We must select element $999$, and the sum is odd.

For $2$nd case: We must select element $1000$, so overall sum is not odd.

For $3$rd case: We can select element $51$.

For $4$th case: We must select both elements $50$ and $51$  — so overall sum is odd.

For $5$th case: We must select all elements  — but overall sum is not odd.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
«Next please», — the princess called and cast an estimating glance at the next groom.

The princess intends to choose the most worthy groom, this is, the richest one. Whenever she sees a groom who is more rich than each of the previous ones, she says a measured «Oh...». Whenever the groom is richer than all previous ones added together, she exclaims «Wow!» (no «Oh...» in this case). At the sight of the first groom the princess stays calm and says nothing.

The fortune of each groom is described with an integer between 1 and 50000. You know that during the day the princess saw *n* grooms, said «Oh...» exactly *a* times and exclaimed «Wow!» exactly *b* times. Your task is to output a sequence of *n* integers *t*1,<=*t*2,<=...,<=*t**n*, where *t**i* describes the fortune of *i*-th groom. If several sequences are possible, output any of them. If no sequence exists that would satisfy all the requirements, output a single number -1.

Input Specification:
The only line of input data contains three integer numbers *n*,<=*a* and *b* (1<=≤<=*n*<=≤<=100,<=0<=≤<=*a*,<=*b*<=≤<=15,<=*n*<=&gt;<=*a*<=+<=*b*), separated with single spaces.

Output Specification:
Output any sequence of integers *t*1,<=*t*2,<=...,<=*t**n*, where *t**i* (1<=≤<=*t**i*<=≤<=50000) is the fortune of *i*-th groom, that satisfies the given constraints. If no sequence exists that would satisfy all the requirements, output a single number -1.

Demo Input:
['10 2 3\n', '5 0 0\n']

Demo Output:
['5 1 3 6 16 35 46 4 200 99', '10 10 6 6 5']

Note:
Let's have a closer look at the answer for the first sample test. 
 -  The princess said «Oh...» (highlighted in bold): 5 1 3 6 16 35 46 4 200 99. -  The princess exclaimed «Wow!» (highlighted in bold): 5 1 3 6 16 35 46 4 200 99.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A group of students has recently been admitted to the Faculty of Computer Sciences at the Berland State University. Now the programming teacher wants to divide them into three subgroups for practice sessions.

The teacher knows that a lot of programmers argue which language is the best. The teacher doesn't want to hear any arguments in the subgroups, so she wants to divide the students into three subgroups so that no pair of students belonging to the same subgroup want to argue.

To perform this division, the teacher asked each student which programming language he likes. There are a students who answered that they enjoy Assembler, b students stated that their favourite language is Basic, and c remaining students claimed that C++ is the best programming language — and there was a large argument between Assembler fans and C++ fans.

Now, knowing that Assembler programmers and C++ programmers can start an argument every minute, the teacher wants to divide the students into three subgroups so that every student belongs to exactly one subgroup, and there is no subgroup that contains at least one Assembler fan and at least one C++ fan. Since teaching a lot of students can be difficult, the teacher wants the size of the largest subgroup to be minimum possible.

Please help the teacher to calculate the minimum possible size of the largest subgroup!

Input

The first line contains one integer t (1 ≤ t ≤ 5) — the number of test cases in the input. Then test cases follow.

Each test case consists of one line containing three integers a, b and c (1 ≤ a, b, c ≤ 1000) — the number of Assembler fans, Basic fans and C++ fans, respectively.

Output

For each test case print one integer — the minimum size of the largest subgroup if the students are divided in such a way that there is no subgroup that contains at least one Assembler fan and at least one C++ fan simultaneously.

Examples

Input


5
3 5 7
4 8 4
13 10 13
1000 1000 1000
13 22 7


Output


5
6
13
1000
14


Input


5
1 3 4
1000 1000 1
4 1 2
325 226 999
939 861 505


Output


3
667
3
517
769

Note

Explanation of the answers for the example 1:

  1. The first subgroup contains 3 Assembler fans and 2 Basic fans, the second subgroup — 5 C++ fans, the third subgroup — 2 C++ fans and 3 Basic fans. 
  2. The first subgroup contains 4 Assembler fans, the second subgroup — 6 Basic fans, the third subgroup — 2 Basic fans and 4 C++ fans. 
  3. The first subgroup contains all Assembler fans, the second subgroup — all Basic fans, the third subgroup — all C++ fans. 
  4. The first subgroup contains all Assembler fans, the second subgroup — all Basic fans, the third subgroup — all C++ fans. 
  5. The first subgroup contains 12 Assembler fans and 2 Basic fans, the second subgroup — 1 Assembler fan and 13 Basic fans, the third subgroup — 7 Basic fans and 7 C++ fans. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Zenyk and Marichka are playing a game taking turns alternatively. They have N piles of stones. In the i^{th} pile, there are A_{i} stones initially. 

Marichka goes first, and removes any non-zero number of stones from any pile.  
After that, in one move, a player can take any number of stones from any pile, but not less than the number of stones taken by the opponent in the previous move. 

The player who cannot make a move loses. If both players play optimally, find the winner of the game.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.

- The first line of each tets case contains single integer N — the number of piles.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} — the numbers of stones in piles initially.

------ Output Format ------ 

For each test case, output a new line containing:
- Marichka if Marichka wins.
- Zenyk if Zenyk wins.

Note that you may print each character in lowercase or uppercase. For example, the strings Zenyk, ZENYK, zenyk, and zEnYK are considered identical.

------ Constraints ------ 

$1 ≤T ≤10^{5}$ 
$1 ≤N ≤10^{5}$
$1 ≤A_{i} ≤10^{9}$
- Sum of $N$ over all test cases doesn't exceed $2 \cdot 10^{5}$

------ subtasks ------ 

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
3
3
1 2 3
2
1 1
1
10

----- Sample Output 1 ------ 
Marichka
Zenyk
Marichka

----- explanation 1 ------ 
For the first testcase, Marichka can take $3$ stones from the last pile in the first move, then Zenyk won't be able to make a move, as each pile will contain less than $3$ stones.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
zscoder loves simple strings! A string *t* is called simple if every pair of adjacent characters are distinct. For example ab, aba, zscoder are simple whereas aa, add are not simple.

zscoder is given a string *s*. He wants to change a minimum number of characters so that the string *s* becomes simple. Help him with this task!

Input Specification:
The only line contains the string *s* (1<=≤<=|*s*|<=≤<=2·105) — the string given to zscoder. The string *s* consists of only lowercase English letters.

Output Specification:
Print the simple string *s*' — the string *s* after the minimal number of changes. If there are multiple solutions, you may output any of them.

Note that the string *s*' should also consist of only lowercase English letters.

Demo Input:
['aab\n', 'caaab\n', 'zscoder\n']

Demo Output:
['bab\n', 'cabab\n', 'zscoder\n']

Note:
none

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