vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Problem Statement

Mr. Takatsuki, who is planning to participate in the Aizu training camp, has a poor house and always tries to save as much paper as possible. She decided to play a ghost leg with other participants to decide the team for the Aizu training camp.

How to make Amidakuji for this training camp is as follows. First, write N vertical bars in parallel on the paper. Then, write the M horizontal bars in order from the top so that they are perpendicular to the vertical bars and the heights of the horizontal bars are all different. For example, the Amida of Sample Input 1 is as shown in Fig. 1.

Here, Mr. Takatsuki, a little dissatisfied expression. It's a waste of paper to write a ghost leg so vertically. You should be able to compress the height more. So, I want her to solve the problem of height compression of Amidakuji shown below.

First, the height of the Amidakuji is the value obtained by counting the horizontal bars that exist at the same height together as the height 1 and counting this to the bottom horizontal bar. Here, it is assumed that each horizontal bar can be freely moved up and down in order to perform height compression. However, it is not permissible to remove or add horizontal bars. The Amidakuji after height compression must meet the following conditions.

* The end points of the horizontal bar do not touch the end points of other horizontal bars.
* The result of tracing the Amidakuji after compression and the result of tracing the Amidakuji before compression match.



FIG. 2 is a compressed version of FIG. The "horizontal bar connecting vertical bars 1 and 2" moves to the top and becomes the same height as the "horizontal bar connecting vertical bars 4 and 5", and these two are height 1. After that, the "horizontal bar connecting the vertical bars 3 and 4" and the "horizontal bar connecting the vertical bars 2 and 3" have different heights, and the total height is 3.

<image>

Compress the height of the given Amidakuji and output the compressed height.

Constraints

* 2 <= N <= 8
* 1 <= M <= 8
* 1 <= ai <= N --1

Input

Each data set is input in the following format.


N M
a1
a2
...
aM


All inputs are integers. N indicates the number of vertical bars and M indicates the number of horizontal bars. Then, the information of the horizontal bar is input over M lines. ai indicates that the i-th horizontal bar connects the vertical bar ai and the vertical bar to the right of it. The i-th horizontal bar exists above the i + 1-th horizontal bar.

Output

Outputs the height of the compressed Amidakuji in one line.

Examples

Input

5 4
4
3
1
2


Output

3


Input

4 3
1
2
3


Output

3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a white sheet of paper lying on a rectangle table. The sheet is a rectangle with its sides parallel to the sides of the table. If you will take a look from above and assume that the bottom left corner of the table has coordinates $(0, 0)$, and coordinate axes are left and bottom sides of the table, then the bottom left corner of the white sheet has coordinates $(x_1, y_1)$, and the top right — $(x_2, y_2)$.

After that two black sheets of paper are placed on the table. Sides of both black sheets are also parallel to the sides of the table. Coordinates of the bottom left corner of the first black sheet are $(x_3, y_3)$, and the top right — $(x_4, y_4)$. Coordinates of the bottom left corner of the second black sheet are $(x_5, y_5)$, and the top right — $(x_6, y_6)$.  [Image] Example of three rectangles. 

Determine if some part of the white sheet can be seen from the above after the two black sheets are placed. The part of the white sheet can be seen if there is at least one point lying not strictly inside the white sheet and strictly outside of both black sheets.


-----Input-----

The first line of the input contains four integers $x_1, y_1, x_2, y_2$ $(0 \le x_1 < x_2 \le 10^{6}, 0 \le y_1 < y_2 \le 10^{6})$ — coordinates of the bottom left and the top right corners of the white sheet.

The second line of the input contains four integers $x_3, y_3, x_4, y_4$ $(0 \le x_3 < x_4 \le 10^{6}, 0 \le y_3 < y_4 \le 10^{6})$ — coordinates of the bottom left and the top right corners of the first black sheet.

The third line of the input contains four integers $x_5, y_5, x_6, y_6$ $(0 \le x_5 < x_6 \le 10^{6}, 0 \le y_5 < y_6 \le 10^{6})$ — coordinates of the bottom left and the top right corners of the second black sheet.

The sides of each sheet of paper are parallel (perpendicular) to the coordinate axes.


-----Output-----

If some part of the white sheet can be seen from the above after the two black sheets are placed, print "YES" (without quotes). Otherwise print "NO".


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

Output
NO

Input
3 3 7 5
0 0 4 6
0 0 7 4

Output
YES

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

Output
YES

Input
0 0 1000000 1000000
0 0 499999 1000000
500000 0 1000000 1000000

Output
YES



-----Note-----

In the first example the white sheet is fully covered by black sheets.

In the second example the part of the white sheet can be seen after two black sheets are placed. For example, the point $(6.5, 4.5)$ lies not strictly inside the white sheet and lies strictly outside of both black sheets.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a set of integer numbers, initially it is empty. You should perform *n* queries.

There are three different types of queries: 
 -  1 *l* *r* — Add all missing numbers from the interval [*l*,<=*r*] -  2 *l* *r* — Remove all present numbers from the interval [*l*,<=*r*] -  3 *l* *r* — Invert the interval [*l*,<=*r*] — add all missing and remove all present numbers from the interval [*l*,<=*r*] 
After each query you should output MEX of the set — the smallest positive (MEX <=≥<=1) integer number which is not presented in the set.

Input Specification:
The first line contains one integer number *n* (1<=≤<=*n*<=≤<=105).

Next *n* lines contain three integer numbers *t*,<=*l*,<=*r* (1<=≤<=*t*<=≤<=3,<=1<=≤<=*l*<=≤<=*r*<=≤<=1018) — type of the query, left and right bounds.

Output Specification:
Print MEX of the set after each query.

Demo Input:
['3\n1 3 4\n3 1 6\n2 1 3\n', '4\n1 1 3\n3 5 6\n2 4 4\n3 1 6\n']

Demo Output:
['1\n3\n1\n', '4\n4\n4\n1\n']

Note:
Here are contents of the set after each query in the first example:
 1.  {3, 4} — the interval [3, 4] is added 1.  {1, 2, 5, 6} — numbers {3, 4} from the interval [1, 6] got deleted and all the others are added 1.  {5, 6} — numbers {1, 2} got deleted

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya claims that he had a paper square. He cut it into two rectangular parts using one vertical or horizontal cut. Then Vasya informed you the dimensions of these two rectangular parts. You need to check whether Vasya originally had a square. In other words, check if it is possible to make a square using two given rectangles.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow.

Each test case is given in two lines.

The first line contains two integers $a_1$ and $b_1$ ($1 \le a_1, b_1 \le 100$) — the dimensions of the first one obtained after cutting rectangle. The sizes are given in random order (that is, it is not known which of the numbers is the width, and which of the numbers is the length).

The second line contains two integers $a_2$ and $b_2$ ($1 \le a_2, b_2 \le 100$) — the dimensions of the second obtained after cutting rectangle. The sizes are given in random order (that is, it is not known which of the numbers is the width, and which of the numbers is the length).


-----Output-----

Print $t$ answers, each of which is a string "YES" (in the case of a positive answer) or "NO" (in the case of a negative answer). The letters in words can be printed in any case (upper or lower).


-----Example-----
Input
3
2 3
3 1
3 2
1 3
3 3
1 3

Output
Yes
Yes
No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After rejecting 10^{100} data structure problems, Errorgorn is very angry at Anton and decided to kill him.

Anton's DNA can be represented as a string a which only contains the characters "ANTON" (there are only 4 distinct characters). 

Errorgorn can change Anton's DNA into string b which must be a permutation of a. However, Anton's body can defend against this attack. In 1 second, his body can swap 2 adjacent characters of his DNA to transform it back to a. Anton's body is smart and will use the minimum number of moves.

To maximize the chance of Anton dying, Errorgorn wants to change Anton's DNA the string that maximizes the time for Anton's body to revert his DNA. But since Errorgorn is busy making more data structure problems, he needs your help to find the best string B. Can you help him?

Input

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

The first and only line of each testcase contains 1 string a (1 ≤ |a| ≤ 100000). a consists of only the characters "A", "N", "O" and "T".

It is guaranteed that the sum of |a| over all testcases does not exceed 100000.

Output

For each testcase, print a single string, b. If there are multiple answers, you can output any one of them. b must be a permutation of the string a.

Example

Input


4
ANTON
NAAN
AAAAAA
OAANTTON


Output


NNOTA
AANN
AAAAAA
TNNTAOOA

Note

For the first testcase, it takes 7 seconds for Anton's body to transform NNOTA to ANTON: 

NNOTA → NNOAT → NNAOT → NANOT → NANTO → ANNTO → ANTNO → ANTON. 

Note that you cannot output strings such as AANTON, ANTONTRYGUB, AAAAA and anton as it is not a permutation of ANTON.

For the second testcase, it takes 2 seconds for Anton's body to transform AANN to NAAN. Note that other strings such as NNAA and ANNA will also be accepted.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Lesha loves listening to music via his smartphone. But the smartphone doesn't have much memory, so Lesha listens to his favorite songs in a well-known social network InTalk.

Unfortunately, internet is not that fast in the city of Ekaterinozavodsk and the song takes a lot of time to download. But Lesha is quite impatient. The song's duration is *T* seconds. Lesha downloads the first *S* seconds of the song and plays it. When the playback reaches the point that has not yet been downloaded, Lesha immediately plays the song from the start (the loaded part of the song stays in his phone, and the download is continued from the same place), and it happens until the song is downloaded completely and Lesha listens to it to the end. For *q* seconds of real time the Internet allows you to download *q*<=-<=1 seconds of the track.

Tell Lesha, for how many times he will start the song, including the very first start.

Input Specification:
The single line contains three integers *T*,<=*S*,<=*q* (2<=≤<=*q*<=≤<=104, 1<=≤<=*S*<=&lt;<=*T*<=≤<=105).

Output Specification:
Print a single integer — the number of times the song will be restarted.

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

Demo Output:
['2\n', '1\n', '1\n']

Note:
In the first test, the song is played twice faster than it is downloaded, which means that during four first seconds Lesha reaches the moment that has not been downloaded, and starts the song again. After another two seconds, the song is downloaded completely, and thus, Lesha starts the song twice.

In the second test, the song is almost downloaded, and Lesha will start it only once.

In the third sample test the download finishes and Lesha finishes listening at the same moment. Note that song isn't restarted in this case.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the last mission, MDCS has successfully shipped N AI robots to Mars. Before they start exploring, system initialization is required so they are arranged in a line. Every robot can be described with three numbers: position (x_i), radius of sight (r_i) and IQ (q_i).

Since they are intelligent robots, some of them will talk if they see each other. Radius of sight is inclusive, so robot can see other all robots in range [x_i - r_i, x_i + r_i]. But they don't walk to talk with anybody, but only with robots who have similar IQ. By similar IQ we mean that their absolute difference isn't more than K. 

Help us and calculate how many pairs of robots are going to talk with each other, so we can timely update their software and avoid any potential quarrel.

Input

The first line contains two integers, numbers N (1 ≤ N ≤ 10^5)  and K (0 ≤ K ≤ 20).

Next N lines contain three numbers each x_i, r_i, q_i (0 ≤ x_i,r_i,q_i ≤ 10^9) — position, radius of sight and IQ of every robot respectively.

Output

Output contains only one number — solution to the problem.

Example

Input

3 2
3 6 1
7 3 10
10 5 8


Output

1

Note

The first robot can see the second, but not vice versa. The first robot can't even see the third. The second and the third robot can see each other and their IQs don't differ more than 2 so only one conversation will happen.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The Zoo in the Grid Kingdom is represented by an infinite grid. The Zoo has *n* observation binoculars located at the *OX* axis. For each *i* between 1 and *n*, inclusive, there exists a single binocular located at the point with coordinates (*i*,<=0). There are *m* flamingos in the Zoo, located at points with positive coordinates. The flamingos are currently sleeping and you can assume that they don't move.

In order to get a good view over the flamingos, each of the binoculars can be independently rotated to face any angle (not necessarily integer). Then, the binocular can be used to observe all flamingos that is located at the straight line passing through the binocular at the angle it is set. In other words, you can assign each binocular a direction corresponding to any straight line passing through the binocular, and the binocular will be able to see all flamingos located on that line.

Today, some kids from the prestigious Codeforces kindergarten went on a Field Study to the Zoo. Their teacher would like to set each binocular an angle to maximize the number of flamingos that can be seen by the binocular. The teacher is very interested in the sum of these values over all binoculars. Please help him find this sum.

Input Specification:
The first line contains two space-separated integers *n* and *m* (1<=≤<=*n*<=≤<=106,<=1<=≤<=*m*<=≤<=250), denoting the number of binoculars and the number of flamingos, respectively.

Then *m* lines follow, the *i*-th line will contain two space-separated integers *x**i* and *y**i* (1<=≤<=*x**i*,<=*y**i*<=≤<=109), which means that the *i*-th flamingo is located at point (*x**i*,<=*y**i*). 

All flamingos will be located at distinct points.

Output Specification:
Print a single integer denoting the maximum total number of flamingos that can be seen by all the binoculars.

Demo Input:
['5 5\n2 1\n4 1\n3 2\n4 3\n4 4\n']

Demo Output:
['11\n']

Note:
This picture shows the answer to the example test case.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a board with a 2 \times N grid.
Snuke covered the board with N dominoes without overlaps.
Here, a domino can cover a 1 \times 2 or 2 \times 1 square.
Then, Snuke decided to paint these dominoes using three colors: red, cyan and green.
Two dominoes that are adjacent by side should be painted by different colors.
Here, it is not always necessary to use all three colors.
Find the number of such ways to paint the dominoes, modulo 1000000007.
The arrangement of the dominoes is given to you as two strings S_1 and S_2 in the following manner:
 - Each domino is represented by a different English letter (lowercase or uppercase).
 - The j-th character in S_i represents the domino that occupies the square at the i-th row from the top and j-th column from the left.

-----Constraints-----
 - 1 \leq N \leq 52
 - |S_1| = |S_2| = N
 - S_1 and S_2 consist of lowercase and uppercase English letters.
 - S_1 and S_2 represent a valid arrangement of dominoes.

-----Input-----
Input is given from Standard Input in the following format:
N
S_1
S_2

-----Output-----
Print the number of such ways to paint the dominoes, modulo 1000000007.

-----Sample Input-----
3
aab
ccb

-----Sample Output-----
6

There are six ways as shown below:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a rectangle in a coordinate plane. The coordinates of the four vertices are (0,0), (W,0), (W,H), and (0,H).
You are given a point (x,y) which is within the rectangle or on its border. We will draw a straight line passing through (x,y) to cut the rectangle into two parts. Find the maximum possible area of the part whose area is not larger than that of the other. Additionally, determine if there are multiple ways to cut the rectangle and achieve that maximum.

-----Constraints-----
 - 1 \leq W,H \leq 10^9
 - 0\leq x\leq W
 - 0\leq y\leq H
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
W H x y

-----Output-----
Print the maximum possible area of the part whose area is not larger than that of the other, followed by 1 if there are multiple ways to cut the rectangle and achieve that maximum, and 0 otherwise.
The area printed will be judged correct when its absolute or relative error is at most 10^{-9}.

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

-----Sample Output-----
3.000000 0

The line x=1 gives the optimal cut, and no other line does.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Among Johnny's numerous hobbies, there are two seemingly harmless ones: applying bitwise operations and sneaking into his dad's office. As it is usually the case with small children, Johnny is unaware that combining these two activities can get him in a lot of trouble.

There is a set $S$ containing very important numbers on his dad's desk. The minute Johnny heard about it, he decided that it's a good idea to choose a positive integer $k$ and replace each element $s$ of the set $S$ with $s \oplus k$ ($\oplus$ denotes the exclusive or operation). 

Help him choose such $k$ that Johnny's dad will not see any difference after his son is done playing (i.e. Johnny will get the same set as before playing). It is possible that no such number exists. It is also possible that there are many of them. In such a case, output the smallest one. Note that the order of elements in a set doesn't matter, i.e. set $\{1, 2, 3\}$ equals to set $\{2, 1, 3\}$.

Formally, find the smallest positive integer $k$ such that $\{s \oplus k | s \in S\} = S$ or report that there is no such number.

For example, if $S = \{1, 3, 4\}$ and $k = 2$, new set will be equal to $\{3, 1, 6\}$. If $S = \{0, 1, 2, 3\}$ and $k = 1$, after playing set will stay the same.


-----Input-----

In the first line of input, there is a single integer $t$ ($1 \leq t \leq 1024$), the number of test cases. In the next lines, $t$ test cases follow. Each of them consists of two lines. 

In the first line there is a single integer $n$ ($1 \leq n \leq 1024$) denoting the number of elements in set $S$. Second line consists of $n$ distinct integers $s_i$ ($0 \leq s_i < 1024$), elements of $S$.

It is guaranteed that the sum of $n$ over all test cases will not exceed $1024$.


-----Output-----

Print $t$ lines; $i$-th line should contain the answer to the $i$-th test case, the minimal positive integer $k$ satisfying the conditions or $-1$ if no such $k$ exists.


-----Example-----
Input
6
4
1 0 2 3
6
10 7 14 8 3 12
2
0 2
3
1 2 3
6
1 4 6 10 11 12
2
0 1023

Output
1
4
2
-1
-1
1023



-----Note-----

In the first test case, the answer is $1$ because it is a minimum positive integer and it satisfies all the conditions.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A rectangular swamp is inhabited by 10 species of frogs. Frogs of species i can jump from hillocks to hillock exactly i units along X-axis or Y-axis. Initially frogs of all types sit at the hillock at coordinates (0, 0). You are given coordinates of all other hillocks in the swamp. Find the largest Manhattan distance from (0, 0) to any hillock to which one of the frogs can travel by jumping between hillocks.

Manhattan distance between (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|.

Input

The first line of the input contains an integer N (1 ≤ N ≤ 100) - the number of hillocks. The following N lines contain the coordinates of the hillocks, formatted as "X Y" ( - 20 ≤ X, Y ≤ 20). All hillocks are distinct, and none of them is located at (0, 0).

Output

Output a single integer — the largest Manhattan distance to any hillock reachable by one of the frogs by jumping between hillocks.

Examples

Input

3
0 1
0 -2
0 3


Output

3


Input

5
0 1
0 2
0 3
2 2
2 4


Output

6


Input

1
18 0


Output

0

Note

In the first example frogs of species 1, 2 and 3 can jump as far as the first, the second and the third hillocks, respectively.

In the second example frog of species 2 can jump to the second hillock, then to the fourth and finally to the fifth.

In the third example no frog can reach the hillock.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The MEX of a set of integers is defined as the smallest non-negative integer that does not belong to this set. For example, $\mathrm{MEX}(\{0,2,3\}) = 1$ and $\mathrm{MEX}(\{1,3\}) = 0$.
Chef has a tree with $N$ nodes (numbered $1$ through $N$). The tree is rooted at node $1$. Chef wants to assign a non-negative integer to each node in such a way that each integer between $0$ and $N-1$ (inclusive) is assigned to exactly one node.
For each node $u$, consider the integers assigned to the nodes in the subtree of $u$ (including $u$); let $a_u$ denote the MEX of these integers. Chef wants $a_1 + a_2 + \ldots + a_N$ to be as large as possible. Find the maximum possible value of this sum.

-----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 a single integer $N$.
- The second line contains $N-1$ space-separated integers $p_1, p_2, \ldots, p_{N-1}$. For each valid $i$, the node $p_i$ is the parent of the node $i+1$.

-----Output-----
For each test case, print a single line containing one integer ― the maximum sum of subtree MEX-s which can be obtained if you assign the weights optimally.

-----Constraints-----
- $1 \le T \le 5$
- $2 \le N \le 10^5$
- $1 \le p_i < i$ for each valid $i$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
2
3
1 1
5
1 1 2 2

-----Example Output-----
4
9

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