vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Polycarp has invited n friends to celebrate the New Year. During the celebration, he decided to take a group photo of all his friends. Each friend can stand or lie on the side.

Each friend is characterized by two values h_i (their height) and w_i (their width). On the photo the i-th friend will occupy a rectangle h_i × w_i (if they are standing) or w_i × h_i (if they are lying on the side).

The j-th friend can be placed in front of the i-th friend on the photo if his rectangle is lower and narrower than the rectangle of the i-th friend. Formally, at least one of the following conditions must be fulfilled:

  * h_j < h_i and w_j < w_i (both friends are standing or both are lying); 
  * w_j < h_i and h_j < w_i (one of the friends is standing and the other is lying). 



For example, if n = 3, h=[3,5,3] and w=[4,4,3], then:

  * the first friend can be placed in front of the second: w_1 < h_2 and h_1 < w_2 (one of the them is standing and the other one is lying); 
  * the third friend can be placed in front of the second: h_3 < h_2 and w_3 < w_2 (both friends are standing or both are lying). 



In other cases, the person in the foreground will overlap the person in the background.

Help Polycarp for each i find any j, such that the j-th friend can be located in front of the i-th friend (i.e. at least one of the conditions above is fulfilled).

Please note that you do not need to find the arrangement of all people for a group photo. You just need to find for each friend i any other friend j who can be located in front of him. Think about it as you need to solve n separate independent subproblems.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of friends.

This is followed by n lines, each of which contains a description of the corresponding friend. Each friend is described by two integers h_i and w_i (1 ≤ h_i, w_i ≤ 10^9) — height and width of the i-th friend, respectively.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case output n integers on a separate line, where the i-th number is the index of a friend that can be placed in front of the i-th. If there is no such friend, then output -1.

If there are several answers, output any.

Example

Input


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


Output


-1 3 -1 
-1 -1 -1 
-1 -1 2 2 
3 3 -1 3 

Note

The first test case is described in the statement.

In the third test case, the following answers are also correct: 

  * [-1, -1, 1, 2]; 
  * [-1, -1, 1, 1]; 
  * [-1, -1, 2, 1]. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string S of length N consisting of ( and ). Your task is to insert some number of ( and ) into S to obtain a correct bracket sequence.

Here, a correct bracket sequence is defined as follows:  
 - () is a correct bracket sequence.
 - If X is a correct bracket sequence, the concatenation of (, X and ) in this order is also a correct bracket sequence.
 - If X and Y are correct bracket sequences, the concatenation of X and Y in this order is also a correct bracket sequence.
 - Every correct bracket sequence can be derived from the rules above.
Find the shortest correct bracket sequence that can be obtained. If there is more than one such sequence, find the lexicographically smallest one.

-----Constraints-----
 - The length of S is N.
 - 1 ≤ N ≤ 100
 - S consists of ( and ).

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

-----Output-----
Print the lexicographically smallest string among the shortest correct bracket sequences that can be obtained by inserting some number of ( and ) into S.

-----Sample Input-----
3
())

-----Sample Output-----
(())


Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Don Drumphet lives in a nice neighborhood, but one of his neighbors has started to let his house go.  Don Drumphet wants to build a wall between his house and his neighbor’s, and is trying to get the neighborhood association to pay for it.  He begins to solicit his neighbors to petition to get the association to build the wall.  Unfortunately for Don Drumphet, he cannot read very well, has a very limited attention span, and can only remember two letters from each of his neighbors’ names.  As he collects signatures, he insists that his neighbors keep truncating their names until two letters remain, and he can finally read them.

Your code will show Full name of the neighbor and the truncated version of the name as an array. If the number of the characters in name is less than or equal to two, it will return an array containing only the name as is"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A subsequence of a string S is a string that can be obtained by deleting zero or more characters from S without changing the order of the remaining characters.
For example, arc, artistic and (an empty string) are all subsequences of artistic; abc and ci are not.
You are given a string A consisting of lowercase English letters.
Find the shortest string among the strings consisting of lowercase English letters that are not subsequences of A.
If there are more than one such string, find the lexicographically smallest one among them.

-----Constraints-----
 - 1 \leq |A| \leq 2 \times 10^5
 - A consists of lowercase English letters.

-----Input-----
Input is given from Standard Input in the following format:
A

-----Output-----
Print the lexicographically smallest string among the shortest strings consisting of lowercase English letters that are not subsequences of A.

-----Sample Input-----
atcoderregularcontest

-----Sample Output-----
b

The string atcoderregularcontest contains a as a subsequence, but not b.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
To plan for Final Day attack on the city of Lanka Sugreev decided to steal the map of the city from the Central Library of Lanka. As Ravan is quiet smart, he has made lot of fake maps and kept them with the real map. Sugreev's spy attacked the library and bought all the maps.

Each of the map is given in the form of Directed Weighted Graph. Each node on the graph denotes a guard post in the city. Let edge weight from node 'i' to node 'j' be denoted by w[i]. If there is an edge from node 'i' to node 'j' then it means that guard post at node i requires at least w[i] more soldiers to break than guard post
 at node j. 

Now it is Sugreev's job to decide which of the maps is a real one and which is the fake one. Sugreev has asked you to help him.
You will be provided a description of map and if map is valid one then print "YES" otherwise print "NO" (quotes for clarity).

Input:

First line will contain T, denoting the number of test cases.

Each test case will contain following:

First line will contain N. number of nodes.

Next line contain M, number of edges

Next M lines will follow.

Each line will contain three integers i, j, w[i], denoting an edge from node i to j having weight w[i] respectively.

Output:

For each Test Case

A single line consisting of the output.

Constraint:

0 < T ≤ 10

0 < N ≤ 100 (10^2)

0 ≤ M ≤ (N*(N-1))

0 < i ≤ N

0 < j ≤ N

0 ≤ w[i] ≤ 100000 (10^5)

Note: No self loop occur in the graph.

SAMPLE INPUT
2

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

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

SAMPLE OUTPUT
YES
NO

Explanation

        2    
(1) - - - - ->(2)
/|\            |
 |             |
 |             | 3
6|             |
 |             |
 |            \|/ 
(4) <---------(3)
        5

Answer: NO

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
A guy named Vasya attends the final grade of a high school. One day Vasya decided to watch a match of his favorite hockey team. And, as the boy loves hockey very much, even more than physics, he forgot to do the homework. Specifically, he forgot to complete his physics tasks. Next day the teacher got very angry at Vasya and decided to teach him a lesson. He gave the lazy student a seemingly easy task: You are given an idle body in space and the forces that affect it. The body can be considered as a material point with coordinates (0; 0; 0). Vasya had only to answer whether it is in equilibrium. "Piece of cake" — thought Vasya, we need only to check if the sum of all vectors is equal to 0. So, Vasya began to solve the problem. But later it turned out that there can be lots and lots of these forces, and Vasya can not cope without your help. Help him. Write a program that determines whether a body is idle or is moving by the given vectors of forces.

Input Specification:
The first line contains a positive integer *n* (1<=≤<=*n*<=≤<=100), then follow *n* lines containing three integers each: the *x**i* coordinate, the *y**i* coordinate and the *z**i* coordinate of the force vector, applied to the body (<=-<=100<=≤<=*x**i*,<=*y**i*,<=*z**i*<=≤<=100).

Output Specification:
Print the word "YES" if the body is in equilibrium, or the word "NO" if it is not.

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

Demo Output:
['NO', 'YES']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has got a robot which is situated on an infinite Cartesian plane, initially in the cell $(0, 0)$. Robot can perform the following four kinds of operations:   U — move from $(x, y)$ to $(x, y + 1)$;  D — move from $(x, y)$ to $(x, y - 1)$;  L — move from $(x, y)$ to $(x - 1, y)$;  R — move from $(x, y)$ to $(x + 1, y)$. 

Vasya also has got a sequence of $n$ operations. Vasya wants to modify this sequence so after performing it the robot will end up in $(x, y)$.

Vasya wants to change the sequence so the length of changed subsegment is minimum possible. This length can be calculated as follows: $maxID - minID + 1$, where $maxID$ is the maximum index of a changed operation, and $minID$ is the minimum index of a changed operation. For example, if Vasya changes RRRRRRR to RLRRLRL, then the operations with indices $2$, $5$ and $7$ are changed, so the length of changed subsegment is $7 - 2 + 1 = 6$. Another example: if Vasya changes DDDD to DDRD, then the length of changed subsegment is $1$. 

If there are no changes, then the length of changed subsegment is $0$. Changing an operation means replacing it with some operation (possibly the same); Vasya can't insert new operations into the sequence or remove them.

Help Vasya! Tell him the minimum length of subsegment that he needs to change so that the robot will go from $(0, 0)$ to $(x, y)$, or tell him that it's impossible.


-----Input-----

The first line contains one integer number $n~(1 \le n \le 2 \cdot 10^5)$ — the number of operations.

The second line contains the sequence of operations — a string of $n$ characters. Each character is either U, D, L or R.

The third line contains two integers $x, y~(-10^9 \le x, y \le 10^9)$ — the coordinates of the cell where the robot should end its path.


-----Output-----

Print one integer — the minimum possible length of subsegment that can be changed so the resulting sequence of operations moves the robot from $(0, 0)$ to $(x, y)$. If this change is impossible, print $-1$.


-----Examples-----
Input
5
RURUU
-2 3

Output
3

Input
4
RULR
1 1

Output
0

Input
3
UUU
100 100

Output
-1



-----Note-----

In the first example the sequence can be changed to LULUU. So the length of the changed subsegment is $3 - 1 + 1 = 3$.

In the second example the given sequence already leads the robot to $(x, y)$, so the length of the changed subsegment is $0$.

In the third example the robot can't end his path in the cell $(x, y)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Little Artem and Time Machine

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Artem has invented a time machine! He could go anywhere in time, but all his thoughts of course are with computer science. He wants to apply this time machine to a well-known data structure: multiset.

Artem wants to create a basic multiset of integers. He wants these structure to support operations of three types:
 1.  Add integer to the multiset. Note that the difference between set and multiset is that multiset may store several instances of one integer. 1.  Remove integer from the multiset. Only one instance of this integer is removed. Artem doesn't want to handle any exceptions, so he assumes that every time remove operation is called, that integer is presented in the multiset. 1.  Count the number of instances of the given integer that are stored in the multiset. 
But what about time machine? Artem doesn't simply apply operations to the multiset one by one, he now travels to different moments of time and apply his operation there. Consider the following example.
 -  First Artem adds integer 5 to the multiset at the 1-st moment of time. -  Then Artem adds integer 3 to the multiset at the moment 5. -  Then Artem asks how many 5 are there in the multiset at moment 6. The answer is 1. -  Then Artem returns back in time and asks how many integers 3 are there in the set at moment 4. Since 3 was added only at moment 5, the number of integers 3 at moment 4 equals to 0. -  Then Artem goes back in time again and removes 5 from the multiset at moment 3. -  Finally Artyom asks at moment 7 how many integers 5 are there in the set. The result is 0, since we have removed 5 at the moment 3. 
Note that Artem dislikes exceptions so much that he assures that after each change he makes all delete operations are applied only to element that is present in the multiset. The answer to the query of the third type is computed at the moment Artem makes the corresponding query and are not affected in any way by future changes he makes.

Help Artem implement time travellers multiset.

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=100<=000) — the number of Artem's queries.

Then follow *n* lines with queries descriptions. Each of them contains three integers *a**i*, *t**i* and *x**i* (1<=≤<=*a**i*<=≤<=3, 1<=≤<=*t**i*,<=*x**i*<=≤<=109) — type of the query, moment of time Artem travels to in order to execute this query and the value of the query itself, respectively. It's guaranteed that all moments of time are distinct and that after each operation is applied all operations of the first and second types are consistent.

Output Specification:
For each ask operation output the number of instances of integer being queried at the given moment of time.

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

Demo Output:
['1\n2\n1\n', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Takahashi Kingdom, there is an archipelago of N islands, called Takahashi Islands.
For convenience, we will call them Island 1, Island 2, ..., Island N.
There are M kinds of regular boat services between these islands.
Each service connects two islands. The i-th service connects Island a_i and Island b_i.
Cat Snuke is on Island 1 now, and wants to go to Island N.
However, it turned out that there is no boat service from Island 1 to Island N, so he wants to know whether it is possible to go to Island N by using two boat services.
Help him.

-----Constraints-----
 - 3 ≤ N ≤ 200 000
 - 1 ≤ M ≤ 200 000
 - 1 ≤ a_i < b_i ≤ N
 - (a_i, b_i) \neq (1, N)
 - If i \neq j, (a_i, b_i) \neq (a_j, b_j).

-----Input-----
Input is given from Standard Input in the following format:
N M
a_1 b_1
a_2 b_2
:
a_M b_M

-----Output-----
If it is possible to go to Island N by using two boat services, print POSSIBLE; otherwise, print IMPOSSIBLE.

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

-----Sample Output-----
POSSIBLE


Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a matrix $a$, consisting of $n$ rows and $m$ columns. Each cell contains an integer in it.

You can change the order of rows arbitrarily (including leaving the initial order), but you can't change the order of cells in a row. After you pick some order of rows, you traverse the whole matrix the following way: firstly visit all cells of the first column from the top row to the bottom one, then the same for the second column and so on. During the traversal you write down the sequence of the numbers on the cells in the same order you visited them. Let that sequence be $s_1, s_2, \dots, s_{nm}$. 

The traversal is $k$-acceptable if for all $i$ ($1 \le i \le nm - 1$) $|s_i - s_{i + 1}| \ge k$.

Find the maximum integer $k$ such that there exists some order of rows of matrix $a$ that it produces a $k$-acceptable traversal.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 16$, $1 \le m \le 10^4$, $2 \le nm$) — the number of rows and the number of columns, respectively.

Each of the next $n$ lines contains $m$ integers ($1 \le a_{i, j} \le 10^9$) — the description of the matrix.


-----Output-----

Print a single integer $k$ — the maximum number such that there exists some order of rows of matrix $a$ that it produces an $k$-acceptable traversal.


-----Examples-----
Input
4 2
9 9
10 8
5 3
4 3

Output
5

Input
2 4
1 2 3 4
10 3 7 3

Output
0

Input
6 1
3
6
2
5
1
4

Output
3



-----Note-----

In the first example you can rearrange rows as following to get the $5$-acceptable traversal:

5 3

10 8

4 3

9 9



Then the sequence $s$ will be $[5, 10, 4, 9, 3, 8, 3, 9]$. Each pair of neighbouring elements have at least $k = 5$ difference between them.

In the second example the maximum $k = 0$, any order is $0$-acceptable.

In the third example the given order is already $3$-acceptable, you can leave it as it is.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Counting Rectangles is Fun

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There is an *n*<=×<=*m* rectangular grid, each cell of the grid contains a single integer: zero or one. Let's call the cell on the *i*-th row and the *j*-th column as (*i*,<=*j*).

Let's define a "rectangle" as four integers *a*,<=*b*,<=*c*,<=*d* (1<=≤<=*a*<=≤<=*c*<=≤<=*n*; 1<=≤<=*b*<=≤<=*d*<=≤<=*m*). Rectangle denotes a set of cells of the grid {(*x*,<=*y*) :<= *a*<=≤<=*x*<=≤<=*c*,<=*b*<=≤<=*y*<=≤<=*d*}. Let's define a "good rectangle" as a rectangle that includes only the cells with zeros.

You should answer the following *q* queries: calculate the number of good rectangles all of which cells are in the given rectangle.

Input Specification:
There are three integers in the first line: *n*, *m* and *q* (1<=≤<=*n*,<=*m*<=≤<=40,<=1<=≤<=*q*<=≤<=3·105). Each of the next *n* lines contains *m* characters — the grid. Consider grid rows are numbered from top to bottom, and grid columns are numbered from left to right. Both columns and rows are numbered starting from 1. 

Each of the next *q* lines contains a query — four integers that describe the current rectangle, *a*, *b*, *c*, *d* (1<=≤<=*a*<=≤<=*c*<=≤<=*n*; 1<=≤<=*b*<=≤<=*d*<=≤<=*m*).

Output Specification:
For each query output an answer — a single integer in a separate line.

Demo Input:
['5 5 5\n00101\n00000\n00001\n01000\n00001\n1 2 2 4\n4 5 4 5\n1 2 5 2\n2 2 4 5\n4 2 5 3\n', '4 7 5\n0000100\n0000010\n0011000\n0000000\n1 7 2 7\n3 1 3 1\n2 3 4 5\n1 2 2 7\n2 2 4 7\n']

Demo Output:
['10\n1\n7\n34\n5\n', '3\n1\n16\n27\n52\n']

Note:
For the first example, there is a 5 × 5 rectangular grid, and the first, the second, and the third queries are represented in the following image.
 -  For the first query, there are 10 good rectangles, five 1 × 1, two 2 × 1, two 1 × 2, and one 1 × 3. -  For the second query, there is only one 1 × 1 good rectangle. -  For the third query, there are 7 good rectangles, four 1 × 1, two 2 × 1, and one 3 × 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Assume that you started to store items in progressively expanding square location, like this for the first 9 numbers:

```
05 04 03
06 01 02
07 08 09
```

And like this for the expanding to include up to the first 25 numbers:

```
17 16 15 14 13
18 05 04 03 12
19 06 01 02 11
20 07 08 09 10
21 22 23 24 25
```

You might easily notice that the first - and innermost - layer containes only one number (`01`), the second one  - immediately around it - contains 8 numbers (number in the `02-09` range) and so on.

Your task is to create a function that given a number `n` simply returns the number of layers required to store up to `n` (included).

```python
layers(1) == 1
layers(5) == 2
layers(25) == 3
layers(30) == 4
layers(50) == 5
```

**Fair warning:** you will always and only get positive integers, but be ready for bigger numbers in the tests!

If you had fun with this, also try some follow up kata: [progressive spiral number branch](https://www.codewars.com/kata/progressive-spiral-number-branch/) and [progressive spiral number distance](https://www.codewars.com/kata/progressive-spiral-number-distance/).

*[Base idea taken from [here](http://adventofcode.com/2017/day/3)]*

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

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
Polycarp loves geometric progressions — he collects them. However, as such progressions occur very rarely, he also loves the sequences of numbers where it is enough to delete a single element to get a geometric progression.

In this task we shall define geometric progressions as finite sequences of numbers *a*1,<=*a*2,<=...,<=*a**k*, where *a**i*<==<=*c*·*b**i*<=-<=1 for some real numbers *c* and *b*. For example, the sequences [2, -4, 8], [0, 0, 0, 0], [199] are geometric progressions and [0, 1, 2, 3] is not.

Recently Polycarp has found a sequence and he can't classify it. Help him to do it. Determine whether it is a geometric progression. If it is not, check if it can become a geometric progression if an element is deleted from it.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=105) — the number of elements in the given sequence. The second line contains the given sequence. The numbers are space-separated. All the elements of the given sequence are integers and their absolute value does not exceed 104.

Output Specification:
Print 0, if the given sequence is a geometric progression. Otherwise, check if it is possible to make the sequence a geometric progression by deleting a single element. If it is possible, print 1. If it is impossible, print 2.

Demo Input:
['4\n3 6 12 24\n', '4\n-8 -16 24 -32\n', '4\n0 1 2 3\n']

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

Note:
none

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