vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Problem I: Train King

Roland has been given a mission of dangerous material transfer by Train King. The material is stored in the station A and subject to being transferred to the station B. He will bring it by direct trains between A and B, one (or zero) unit per ride.

Your task is to write a program to find out the most optimal way of his bringing. Your program will receive the timetable of trains on the mission day and should report how many units of material can be transferred at the end. Be aware that there can be trains which can go to the past time or the same time which train leaved the station.

Each train consists of one or more cars. Roland is disallowed to ride the same car of the same train multiple times. This restriction avoids time paradox. He is still allowed to get on a different car, though. You can assume he can change trains instantly.



Input

The first line contains two integers NAB and NBA (0 <= NAB, 0 <= NBA and NAB + NBA <= 50). NAB denotes the number of trains from A to B; NBA denotes the number from B to A.

The next NAB lines describe the information about trains from A to B. Each line gives the information of one train with three integers Ci, Di and Ai (1 <= Ci <= 10, 0 <= Di, Ai < 86400) : the number of cars, the departure time, and the arrival time.

The next NBA lines describe the information about trains from B to A. The information is given in the same format.

Output

Print the maximum amount, in units, of dangerous material that can be transferred.

Examples

Input

1 1
10 100 0
10 100 0


Output

10


Input

5 5
10 0 100
10 200 300
10 400 500
10 600 700
10 800 900
10 100 200
10 300 400
10 500 600
10 700 800
10 900 1000


Output

5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N trees in a particular region of forest with the trees number from 1 to N. Tarzan, our hero is standing on Tree Number 1. Tarzan wants to have a sea view from the top of a tree to see whether his girlfriend has arrived at the shore or not. But the shore is visible only from tree number N. 

So, he needs to reach tree number N without climbing down from any of the tree.. He can jump from any tree to any other tree except for some pairs of trees which are not close enough. Also, all the other trees in the forest except for these N trees are too far away from these N trees, which means he CANNOT jump from one of the N trees to any tree which is not part of the given set. (N trees). 

If it is not possible to reach tree N by the above method, you should print “HOHA HOHA” (without quotes) which is how Tarzan shows his frustration. If it is possible to reach tree N, then print a single integer representing the minimum number of jumps for the same.

Input format : First line has two integers N and M, N the number of trees, and M, the number of trees which are not close enough (1 ≤ N ≤ 1000, M ≤ 1000000). The next M lines contains two integers t1 and t2 each which means the pair t1 and t2 are not close enough. (1 ≤ t1, t2 ≤ N). 

Output format : If it is possible to reach tree N, then print a single integer representing the minimum number of jumps for the same. Else print “HOHA HOHA”.

Setter : SP Harish

SAMPLE INPUT
5 4
1 5
2 4
2 5
3 4

SAMPLE OUTPUT
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You may have helped Chef and prevented Doof from destroying the even numbers. But, it has only angered Dr Doof even further. However, for his next plan, he needs some time. Therefore, Doof has built $N$ walls to prevent Chef from interrupting him. You have to help Chef by telling him the number of walls he needs to destroy in order to reach Dr Doof.
Formally, the whole area can be represented as the first quadrant with the origin at the bottom-left corner. Dr. Doof is located at the origin $(0, 0)$. There are $N$ walls, the i-th wall is a straight line segment joining the points $(a_i, 0)$ and $(0, a_i)$. For every initial position of Chef $(x_j, y_j)$, find the number of walls he needs to break before reaching Doof. Obviously, chef can't start from a point on the wall. Therefore, if $(x_j, y_j)$ lies on any of the given walls, print $-1$ in a new line.

-----Input-----
- First line contains $T$, denoting the number of testcases.
- The first line of every test case contains a single integer $N$ denoting the number of walls Dr Doof has built.
- The next line contains $N$ space separated distinct integers each denoting $a_i$.
- The next line contains a single integer $Q$ denoting the number of times Chef asks for your help.
- The next $Q$ lines contains two space separated integers $x_j$ and $y_j$, each denoting the co-ordinates of the starting point of Chef.

-----Output-----
For each query, print the number of walls Chef needs to break in order to reach Dr Doof in a separate line. If Chef tries to start from a point on any of the walls, print $-1$.

-----Constraints-----
- $1 \leq T \leq 2 * 10^2$
- $1 \leq N, Q \leq 2 * 10^5$
- $1 \leq a_i \leq 10^9$
- $0 \leq x_j, y_j \leq 10^9$
- $a_1 < a_2 < a_3 < .... < a_N$
- Sum of $N$ and $Q$ over all testcases for a particular test file does not exceed $2 * 10^5$

-----Sample Input-----
1
2
1 3
5
0 0
2 0
0 4
1 1
1 2

-----Sample Output-----
0
1
2
1
-1

-----Explanation-----
The sample input can be represented by the graph given below:

If Chef starts from $(0, 0)$, he can reach Dr Doof without destroying any wall.

If Chef starts from $(2, 0)$, he has to destroy the $1st$ wall.

If Chef starts from $(0, 4)$, he has to destroy both the walls.

If Chef starts from $(1, 1)$, he has to destroy the $1st$ wall.

As $(1, 2)$ lies on the second wall, the answer is $-1$ for the last query.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A modified KP number is a positive whole number n with d digits, such that when we split its square into two pieces - a right hand piece r with d digits and a left hand piece l that contains the remaining d or d−1 digits, the sum of the pieces is equal to the original number (i.e. l + r = n).

Note: r may have leading zeros.

Here's an explanation about the ORIGINAL KP Number. A KP number for a given base is a non-negative integer, the representation of whose square in that base can be split into two parts that add up to the original number again. For instance, 45 is a KP number, because 45² = 2025 and 20+25 = 45.

You are given the two positive integers p and q, where p is lower than q. Write a program to determine how many KP numbers are there in the range between p and q (both inclusive) and display them all.

INPUT

There will be two lines of input: p, lowest value q, highest value.

OUTPUT

Output each KP number in the given range, space-separated on a single line. If no KP numbers exist in the given range, print INVALID RANGE.

CONSTRAINTS

0<p<q<100000

SAMPLE INPUT
1
100

SAMPLE OUTPUT
1 9 45 55 99

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are N integers A_1,\ldots,A_N.
Find the sum of A_i \times A_j over all pairs (i,j) such that 1\leq i < j \leq N, modulo (10^9+7).

-----Constraints-----
 - 2 \leq N \leq 2\times 10^5
 - 0 \leq A_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 \ldots A_N

-----Output-----
Print \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} A_i A_j, modulo (10^9+7).

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

-----Sample Output-----
11

We have 1 \times 2 + 1 \times 3 + 2 \times 3 = 11.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Monisha likes to paint. She has painted $N$ paintings (numbered $1$ through $N$) and wants to choose some subset of these paintings for an exhibition. For each valid $i$, the $i$-th painting has beauty $b_i$ and the probability that it will be displayed at the exhibition is $p_i$. Each painting is chosen or excluded from the exhibition independently randomly.
The beauty of the resulting exhibition is the bitwise XOR of the beauties of all displayed paintings. If no paintings are displayed, the XOR is $0$.
Monisha wants to find out how beautiful her exhibition is going to be. Help her compute the expected value of the beauty of the exhibition.

-----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$ space-separated integers $b_1, b_2, \ldots, b_N$.
- The third line contains $N$ space-separated real numbers $p_1, p_2, \ldots, p_N$. Each of these numbers is given with at most five digits after the decimal point.

-----Output-----
For each test case, print a single line containing one real number — the expected beauty of the exhibition. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

-----Constraints-----
- $1 \le N \le 10^5$
- $0 \le b_i \le 10^9$ for each valid $i$
- $0 \le p_i \le 1$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $4 \cdot 10^5$

-----Example Input-----
2
3
5 6 2
1.0 0.0 0.5
4
2 2 2 2
0.5 0.5 0.5 0.5

-----Example Output-----
6.000000000000000
1.000000000000000

-----Explanation-----
Example case 1: The first painting must be displayed at the exhibition, the second one must be excluded. If the third painting is displayed (with probability $0.5$), the beauty is $5 \oplus 2 = 7$; if it is excluded (with probability $0.5$), the beauty is $5$. The expected beauty is $0.5 \cdot 5 + 0.5 \cdot 7 = 6$.
Example case 2: If there is an odd number of paintings at the exhibition, the beauty is $2$; this has a probability of $0.5$. If there is an even number of paintings, the beauty is $0$ (with probability $0.5$), so the expected beauty is $0.5 \cdot 0 + 0.5 \cdot 2 = 1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array a of length n consisting of zeros. You perform n actions with this array: during the i-th action, the following sequence of operations appears:

  1. Choose the maximum by length subarray (continuous subsegment) consisting only of zeros, among all such segments choose the leftmost one; 
  2. Let this segment be [l; r]. If r-l+1 is odd (not divisible by 2) then assign (set) a[(l+r)/(2)] := i (where i is the number of the current action), otherwise (if r-l+1 is even) assign (set) a[(l+r-1)/(2)] := i. 



Consider the array a of length 5 (initially a=[0, 0, 0, 0, 0]). Then it changes as follows:

  1. Firstly, we choose the segment [1; 5] and assign a[3] := 1, so a becomes [0, 0, 1, 0, 0]; 
  2. then we choose the segment [1; 2] and assign a[1] := 2, so a becomes [2, 0, 1, 0, 0]; 
  3. then we choose the segment [4; 5] and assign a[4] := 3, so a becomes [2, 0, 1, 3, 0]; 
  4. then we choose the segment [2; 2] and assign a[2] := 4, so a becomes [2, 4, 1, 3, 0]; 
  5. and at last we choose the segment [5; 5] and assign a[5] := 5, so a becomes [2, 4, 1, 3, 5]. 



Your task is to find the array a of length n after performing all n actions. Note that the answer exists and unique.

You have to answer t independent test cases.

Input

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

The only line of the test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of a.

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

Output

For each test case, print the answer — the array a of length n after performing n actions described in the problem statement. Note that the answer exists and unique.

Example

Input


6
1
2
3
4
5
6


Output


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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef wants to store some important numerical data on his personal computer. He is using a new data type that can store values only from 0 till N both inclusive. If this data type receives a value greater than N then it is cyclically converted to fit into the range 0 to N.
For example: 
Value N+1 will be stored as 0.
Value N+2 will be stored as 1. 

and so on...

Given X, the value chef wants to store in this new data type. Determine what will be the actual value in memory after storing X.

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

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains a single line of input, two space separated integers N, X - the maximum value a data type can store and the value Chef wants to store in the data type respectively.

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

For each testcase, output in a single line the value which will be actually stored in memory.

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

$1 ≤ T ≤ 3000$
$1 ≤ N ≤ 50$
$0 ≤ X ≤ 50$

----- Sample Input 1 ------ 
5
15 0
15 10
11 12
27 37
50 49
----- Sample Output 1 ------ 
0
10
0
9
49
----- explanation 1 ------ 
Test Case $1$: The data type can store values from $0$ to $15$. If we try to put $0$ in this data type, then the stored value will be the same, that is $0$.

Test Case $2$: The data type can store values from $0$ to $15$. If we try to put $10$ in this data type, then the stored value will be the same, that is $10$.

Test Case $3$: The data type can store values from $0$ to $11$. If we try to put $12$ in this data type, then the stored value will cyclically come back to $0$. Hence the output is $0$.

Test Case $4$: The data type can store values from $0$ to $27$. If we try to put $37$ in this data type, then the stored value will cyclically convert to $9$. Hence the output is $9$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array A of size N. 

You can do the following operation on the array:
Pick any 2 distinct indices i and j such that A_{i}=A_{j};
Change all the elements between the indices i and j to A_{i}, i.e, for all k (i ≤ k ≤ j), set A_{k}=A_{i}.

Find the minimum number of operations required to sort the array in non-decreasing order. If it is not possible to sort the array, print -1 instead.

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

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, the minimum number of operations required to sort the array. If it is not possible to sort the array, print -1 instead.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$0 ≤ A_{i} ≤ N $
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
6
1 2 1 3 4 3
3
3 1 2
----- Sample Output 1 ------ 
2
-1
----- explanation 1 ------ 
Test Case $1$: We can sort the array using $2$ operations. 
- In the first operation select indices $1$ and $3$. After this operation, the array will be $A = [1,1,1,3,4,3]$.
- In the second operation select indices $4$ and $6$. After this operation, the array will be $A = [1,1,1,3,3,3]$.

Thus, the array is sorted using $2$ operations. It can be proven that the array cannot be sorted in less than $2$ operations.

Test Case $2$: It is not possible to sort the array using any number of operations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day Alice was cleaning up her basement when she noticed something very curious: an infinite set of wooden pieces! Each piece was made of five square tiles, with four tiles adjacent to the fifth center tile:  [Image]  By the pieces lay a large square wooden board. The board is divided into $n^2$ cells arranged into $n$ rows and $n$ columns. Some of the cells are already occupied by single tiles stuck to it. The remaining cells are free.

Alice started wondering whether she could fill the board completely using the pieces she had found. Of course, each piece has to cover exactly five distinct cells of the board, no two pieces can overlap and every piece should fit in the board entirely, without some parts laying outside the board borders. The board however was too large for Alice to do the tiling by hand. Can you help determine if it's possible to fully tile the board?


-----Input-----

The first line of the input contains a single integer $n$ ($3 \leq n \leq 50$) — the size of the board.

The following $n$ lines describe the board. The $i$-th line ($1 \leq i \leq n$) contains a single string of length $n$. Its $j$-th character ($1 \leq j \leq n$) is equal to "." if the cell in the $i$-th row and the $j$-th column is free; it is equal to "#" if it's occupied.

You can assume that the board contains at least one free cell.


-----Output-----

Output YES if the board can be tiled by Alice's pieces, or NO otherwise. You can print each letter in any case (upper or lower).


-----Examples-----
Input
3
#.#
...
#.#

Output
YES

Input
4
##.#
#...
####
##.#

Output
NO

Input
5
#.###
....#
#....
###.#
#####

Output
YES

Input
5
#.###
....#
#....
....#
#..##

Output
NO



-----Note-----

The following sketches show the example boards and their tilings if such tilings exist:  [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef and Paja are bored, so they are playing an infinite game of ping pong. The rules of the game are as follows:
- The players play an infinite number of games. At the end of each game, the player who won it scores a point.
- In each game, one of the players serves. Chef serves in the first game.
- After every $K$ points are scored (regardless of which players scored them), i.e. whenever $K$ games have been played since the last time the serving player changed, the player that serves in the subsequent games changes: if Chef served in the game that just finished, then Paja will serve in the next game and all subsequent games until the serving player changes again; if Paja served, then Chef will serve.
The players got a little too caught up in the game and they forgot who is supposed to serve in the next game. Will you help them determine that? So far, Chef has scored $X$ points and Paja has scored $Y$ points.

-----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 and only line of each test case contains three space-separated integers $X$, $Y$ and $K$.

-----Output-----
For each test case, print a single line containing the string "Chef" if Chef is supposed to serve next or "Paja" otherwise (without quotes).

-----Constraints-----
- $1 \le T \le 50$
- $0 \le X, Y \le 10^9$
- $1 \le K \le 10^9$

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

-----Example Input-----
3
1 3 3
5 7 2
38657 76322 564

-----Example Output-----
Paja
Chef
Paja

-----Explanation-----
Example case 1: Chef served for the first three games, after that Paja started serving. He only served in one game, so he is supposed to serve next.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
KenKen is a popular logic puzzle developed in Japan in 2004. It consists of an $n \times n$ grid divided up into various non-overlapping sections, where each section is labeled with an integer target value and an arithmetic operator. The object is to fill in the entire grid with the numbers in the range 1 to $n$ such that
 - no number appears more than once in any row or column
 - in each section you must be able to reach the section’s target using the numbers in the section and the section’s arithmetic operator

For this problem we are only interested in single sections of a KenKen puzzle, not the entire puzzle. Two examples of sections from an $8 \times 8$ KenKen puzzle are shown below along with some of their possible assignments of digits.

 Figure C.1 

Note that while sections labeled with a subtraction or division operator can consist of only two grid squares, those labeled with addition or multiplication can have any number. Also note that in a $9 \times 9$ puzzle the first example would have two more solutions, each involving the numbers $9$ and $2$. Finally note that in the first solution of the second section you could not swap the $1$ and $4$ in the first row, since that would result in two $1$’s in the same column.

You may be wondering: for a given size KenKen puzzle and a given section in the puzzle, how many valid ways are there to fill in the section? Well, stop wondering and start programming!



-----Input-----
The input will start with a single line of the form $n$ $m$ $t$ $op$, where $n$ is the size of the KenKen puzzle containing the section to be described, $m$ is the number of grid squares in the section, $t$ is the target value and $op$ is either ‘+’, ‘-’, ‘*’ or ‘/’ indicating the arithmetic operator to use for the section.

Next will follow $m$ grid locations of the form $r$ $c$, indicating the row and column number of the grid square. These grid square locations will take up one or more lines.

All grid squares in a given section will be connected so that you can move from any one square in the section to any other by crossing shared lines between grid squares.

The values of $n$, $m$ and $t$ will satisfy $4\leq n\leq 9$, $2 \leq m \leq 10$, $0 < t \le 3 \cdot 10^8$ and $1 \leq r,c \leq n$.

-----Output-----
Output the number of valid ways in which the section could be filled in for a KenKen puzzle of the given size.

-----Examples-----
Sample Input 1:
8 2 7 -
1 1 1 2
Sample Output 1:
2

Sample Input 2:
9 2 7 -
1 1 1 2
Sample Output 2:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.
Given a row x col grid of integers, how many 3 x 3 "magic square" subgrids are there?  (Each subgrid is contiguous).
 
Example 1:

Input: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:

while this one is not:

In total, there is only one magic square inside the given grid.

Example 2:
Input: grid = [[8]]
Output: 0

Example 3:
Input: grid = [[4,4],[3,3]]
Output: 0

Example 4:
Input: grid = [[4,7,8],[9,5,1],[2,3,6]]
Output: 0

 
Constraints:

row == grid.length
col == grid[i].length
1 <= row, col <= 10
0 <= grid[i][j] <= 15

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