vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In India, every individual is charged with income tax on the total income each year. This tax is applied to specific ranges of income, which are called income tax slabs. The slabs of income tax keep changing from year to year. This fiscal year (2020-21), the tax slabs and their respective tax rates are as follows:Total income (in rupees)Tax rateup to Rs. 250,0000%from Rs. 250,001 to Rs. 500,0005%from Rs. 500,001 to Rs. 750,00010%from Rs. 750,001 to Rs. 1,000,00015%from Rs. 1,000,001 to Rs. 1,250,00020%from Rs. 1,250,001 to Rs. 1,500,00025%above Rs. 1,500,00030%
See the sample explanation for details on how the income tax is calculated.
You are given Chef's total income: $N$ rupees (Rs.). Find his net income. The net income is calculated by subtracting the total tax (also called tax reduction) from the total income. Note that you do not need to worry about any other kind of tax reductions, only the one described above.

-----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 a single integer $N$.

-----Output-----
For each test case, print a single line containing one integer — Chef's net income.

-----Constraints-----
- $1 \le T \le 10^3$
- $0 \le N \le 10^7$
- $N$ is a multiple of $100$

-----Example Input-----
2
600000
250000

-----Example Output-----
577500
250000

-----Explanation-----
Example case 1: We know that the total income is Rs. $6$ lakh ($1$ lakh rupees = $10^5$ rupees). The total tax for each slab is calculated as follows:
- Up to $2.5$ lakh, the tax is Rs. $0$, since the tax rate is $0$ percent.
- From above Rs. $2.5$ lakh to Rs. $5$ lakh, the tax rate is $5$ percent. Therefore, this tax is $0.05 \cdot (500,000-250,000)$, which is Rs. $12,500$.
- From above Rs. $5$ lakh to Rs. $6$ lakh, the tax rate is $10$ percent. Therefore, this tax is $0.10 \cdot (600,000-500,000)$, which is Rs. $10,000$.
- Summing them up, we get that the total tax on Chef's whole income is Rs. $22,500$. Since the net income is the total income minus the tax reduction, it is Rs. $600,000$ minus Rs. $22,500$, which is Rs. $577,500$.
Example case 2: For income up to Rs. $2.5$ lakh, we have no tax, so the net income is the same as the total income: Rs. $2.5$ lakh.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A boy PCK had N straight iron bars, which were serially indexed. Unfortunately, the first M bars (0 ≤ M ≤ N) among them were bent during transportation. They all suffered a perpendicular bend at one point.

He is planning to make a cube using a set of bars selected using the following rules: X bars from bent ones, Y bars from straight ones, where 2X + Y = 12. Any two bars can be jointed only at the apexes of the cube. He wants to count how many types of rectangular parallelepipeds (hereafter RP) he can make using these bars.

Make a program to count out types (different shapes) of RPs that PCK can make using the following information: the number of bars and length of each one, position of the bend, and the number of bars to be used to construct an RP. Note that any two RPs similar in shape are considered identical: namely if the length of three defining sides of two RPs coincide if arranged in increasing/decreasing order (e.g., three sides of RP i and j are A_i, B_i, C_i, and A_j, B_j and C_j in increasing order, then the relations A_i = A_j, B_i = B_j, and C_i = C_j hold. Note also that the bars are sufficiently thin to allow you to consider them as idealized lines.



Input

The input is given in the following format.


N M X Y
a_1
a_2
:
a_N
b_1
b_2
:
b_M


The first line provides the total number of iron bars and bent bars, and those straight and bent bars used to construct an RP: N (6 ≤ N ≤ 6000), M (0 ≤ M ≤ N), X (0 ≤ X ≤ 6), and Y (0 ≤ Y ≤ 12). The following relations always hold for them: 2X+Y=12, X+Y ≤ N, X ≤ M. Each of the subsequent N lines provides the length of the i-th bar a_i (1 ≤ a_i ≤ 6000) in integers. Furthermore, each of the subsequent M lines provides the location at which the i-th bent bar suffered a perpendicular bend b_i (1 ≤ b_i ≤ 3000) in centimeters from one end of the bar (note: 1 ≤ a_i-b_i ≤ 3000).

Output

Output the number of constructible rectangular parallelepipeds.

Example

Input

18 8 3 6
4
3
3
3
3
2
2
2
1
1
1
1
1
2
2
3
3
3
1
1
1
1
1
1
1
1


Output

3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice has recently started playing Chess. Her current rating is X. She noticed that when she wins a game, her rating increases by 8 points.

Can you help Alice in finding out the minimum number of games she needs to win in order to make her rating greater than or equal to Y?

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

- The first line of input will contain an integer T — the number of test cases. The description of T test cases follows.
- The first line of each test case contains two integers X and Y, as described in the problem statement. 

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

For each test case, output the minimum number of games that Alice needs to win in order to make her rating greater than or equal to Y.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ X ≤ Y ≤ 10^{4}$

----- Sample Input 1 ------ 
4
10 10
10 17
10 18
10 19

----- Sample Output 1 ------ 
0
1
1
2
----- explanation 1 ------ 
Test case $1$: Since Alice's current rating $X$ is already equal to her desired rating $Y$, she doesn't need to win any game. 

Test case $2$: Alice's current rating is $10$. After winning $1$ game, her rating will become $10+8=18$, which is greater than her desired rating of $17$. Thus, she has to win at least $1$ game.

Test case $3$: Alice's current rating is $10$. After winning $1$ game, her rating will become $10+8=18$, which is equal to her desired rating of $18$. Thus, she has to win at least $1$ game. 

Test case $4$: Alice's current rating is $10$. After winning $1$ game, her rating will become $18$, which is less than her desired rating of $19$. She will need to win one more game in order to make her rating $26$, which is greater than $19$. Thus, she has to win at least $2$ games.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A mobile phone company ACMICPC (Advanced Cellular, Mobile, and Internet-Connected Phone Corporation) is planning to set up a collection of antennas for mobile phones in a city called Maxnorm. The company ACMICPC has several collections for locations of antennas as their candidate plans, and now they want to know which collection is the best choice.

for this purpose, they want to develop a computer program to find the coverage of a collection of antenna locations. Each antenna Ai has power ri, corresponding to "radius". Usually, the coverage region of the antenna may be modeled as a disk centered at the location of the antenna (xi, yi) with radius ri. However, in this city Maxnorm such a coverage region becomes the square [xi − ri, xi + ri] × [yi − ri, yi + ri]. In other words, the distance between two points (xp, yp) and (xq, yq) is measured by the max norm max{ |xp − xq|, |yp − yq|}, or, the L∞ norm, in this city Maxnorm instead of the ordinary Euclidean norm √ {(xp − xq)2 + (yp − yq)2}.

As an example, consider the following collection of 3 antennas


4.0 4.0 3.0
5.0 6.0 3.0
5.5 4.5 1.0


depicted in the following figure

<image>

where the i-th row represents xi, yi ri such that (xi, yi) is the position of the i-th antenna and ri is its power. The area of regions of points covered by at least one antenna is 52.00 in this case.

Write a program that finds the area of coverage by a given collection of antenna locations.



Input

The input contains multiple data sets, each representing a collection of antenna locations. A data set is given in the following format.



n
x1 y1 r1
x2 y2 r2
. . .
xn yn rn



The first integer n is the number of antennas, such that 2 ≤ n ≤ 100. The coordinate of the i-th antenna is given by (xi, yi), and its power is ri. xi, yi and ri are fractional numbers between 0 and 200 inclusive.

The end of the input is indicated by a data set with 0 as the value of n.

Output

For each data set, your program should output its sequence number (1 for the first data set, 2 for the second, etc.) and the area of the coverage region. The area should be printed with two digits to the right of the decimal point, after rounding it to two decimal places.

The sequence number and the area should be printed on the same line with no spaces at the beginning and end of the line. The two numbers should be separated by a space.

Example

Input

3
4.0 4.0 3.0
5.0 6.0 3.0
5.5 4.5 1.0
2
3.0 3.0 3.0
1.5 1.5 1.0
0


Output

1 52.00
2 36.00

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.
Does a tree with n vertices that satisfies the following conditions exist?
 - The vertices are numbered 1,2,..., n.
 - The edges are numbered 1,2,..., n-1, and Edge i connects Vertex u_i and v_i.
 - If the i-th character in s is 1, we can have a connected component of size i by removing one edge from the tree.
 - If the i-th character in s is 0, we cannot have a connected component of size i by removing any one edge from the tree.
If such a tree exists, construct one such tree.

-----Constraints-----
 - 2 \leq n \leq 10^5
 - s is a string of length n consisting of 0 and 1.

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

-----Output-----
If a tree with n vertices that satisfies the conditions does not exist, print -1.
If a tree with n vertices that satisfies the conditions exist, print n-1 lines.
The i-th line should contain u_i and v_i with a space in between.
If there are multiple trees that satisfy the conditions, any such tree will be accepted.

-----Sample Input-----
1111

-----Sample Output-----
-1

It is impossible to have a connected component of size n after removing one edge from a tree with n vertices.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The 1941 October Revolution Parade of November $7^{th}$, 1941, taking place in Moscow, Soviet Union, was a parade in honor of the October Revolution 24 years ealier. It was one of the most memorable parade because of the serious circumstance at that time: Soviet’s forces had constantly been dominated since the last 4 months, and Moscow was surrounded by Nazi under an extremely high pressure. Many soldiers joined that parade, and immediately rushed into the battle field after then. The winning against Nazi later pushed Hitler’s forces very far away from Moscow and completely destroyed his Barbarossa plan…

In order to ensure safety for the parade, Stalin gathered information about the positions of Nazi’s troops. He knew that Nazi’s troops can be depicted as $N$ points on the Cartesian plane. He was also aware of $S$ Soviet’s defending castles, which can be represented by $S$ points.

Stalin thought that one castle was in danger, if there exist a group of four Nazi’s troops, which forms a non-degenerate quadrilateral and the castle lies inside or on its border. Recall that a quadrilateral is non-degenerate iff no three of its vertices are collinear, and its edges do not intersect (with the exception that edges can intersect at vertices). Stalin wanted to know how many castles were in danger, so that he can send a suitable protection for them.

-----Input-----
 - The first line of the input contains one integer $N$ $(4 \leq N \leq 1000)$ - the number of Nazi’s tropps.
 - Each of the next $N$ lines contains two integers $x$ and $y$ $(0 \leq x, y \leq 10^6)$ representing one point where a Nazi’s troop took place.
 - The next line contains one integer $S$ $(1 \leq S \leq 1000)$ - the number of Soviet castles.
 - Each of the next $S$ lines contains two integers $x$ and $y$ $(0 \leq x, y \leq 10^6)$ representing position of one castle.

It is guaranteed that all given points are distinct.

-----Output-----
Write in one line the number castles which were in danger.




-----Sample Clarification-----
The $1^{st}$ sample corresponds to the following figure. Blue points represent Nazi troops’ locations, oranges points represent in-danger castles, green points represent non in-danger castles.

The $2^{nd}$ sample corresponds to the following figure. Note that the quadrilateral is degenerated, so no castle is in danger.

-----Examples-----
Sample Input:
4
0 1
3 7
4 5
6 5
9
1 4
1 6
2 3
2 5
3 5
3 6
4 8
5 4
6 3
Sample Output:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have been recently hired as a developer in CodeChef. Your first mission is to implement a feature that will determine the number of submissions that were judged late in a contest.
There are $N$ submissions, numbered $1$ through $N$. For each valid $i$, the $i$-th submission was submitted at time $S_i$ and judged at time $J_i$ (in minutes). Submitting and judging both take zero time. Please determine how many submissions received their verdicts after a delay of more than $5$ minutes.

-----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 the input contains a single integer $N$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $S_i$ and $J_i$.

-----Output-----
For each test case, print a single line containing one integer — the number of submissions for which the judging was delayed by more than 5 minutes.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N \le 100$
- $1 \le S_i \le J_i \le 300$ for each valid $i$

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

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

-----Example Output-----
2

-----Explanation-----
Example case 1: The delays of the respective submissions are $2$ minutes, $0$ minutes, $6$ minutes, $10$ minutes and $5$ minutes. Only submissions $3$ and $4$ are delayed by more than $5$ minutes, hence the answer is $2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Instead of paying attention in class, Luka is killing time playing with numbers again. This time, he wrote $N$ non-negative integers so that they form a ring (circle). After that he formed a new ring by adding to each number its two neighbours.

The teacher noticed this and took away the first piece of paper, with the original ring. This did not trouble Luka much because he knows he can use the other ring to reconstruct the original.

Write a program that solves Luka’s problem.

-----Input-----
The first line contains the integer $N$ $(3 \le N \le 10000)$, the number of integers in the ring.

Each of the following lines contains an integer less than $10^9$ (one billion). These numbers, in order, form the second ring.

The input will be such that a solution, although not necesarily unique, will always exist.

-----Output-----
Output the original ring on $N$ lines. The numbers must be non-negative.

Rotating the ring is not allowed. For example, the sum of the first three output numbers must be equal to the second number in the input ring.

Note: the solution need not be unique.

-----Examples-----
Sample Input 1:
3
5
5
5
Sample Output 1:
2
1
2

Sample Input 2:
4
20
15
17
14
Sample Output 2:
5
8
2
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string str, convert the first letter of each word in the string to uppercase. 
Example 1:
Input:
str = "i love programming"
Output: "I Love Programming"
Explanation:
'I', 'L', 'P' are the first letters of 
the three words.
Your Task:  
You dont need to read input or print anything. Complete the function transform() which takes s as input parameter and returns the transformed string.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N) to store resultant string  
Constraints:
1 <= N <= 10^{4}
The original string str only consists of lowercase alphabets and spaces to separate words.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a rectangle grid. That grid's size is n × m. Let's denote the coordinate system on the grid. So, each point on the grid will have coordinates — a pair of integers (x, y) (0 ≤ x ≤ n, 0 ≤ y ≤ m).

Your task is to find a maximum sub-rectangle on the grid (x_1, y_1, x_2, y_2) so that it contains the given point (x, y), and its length-width ratio is exactly (a, b). In other words the following conditions must hold: 0 ≤ x_1 ≤ x ≤ x_2 ≤ n, 0 ≤ y_1 ≤ y ≤ y_2 ≤ m, $\frac{x_{2} - x_{1}}{y_{2} - y_{1}} = \frac{a}{b}$.

The sides of this sub-rectangle should be parallel to the axes. And values x_1, y_1, x_2, y_2 should be integers. [Image] 

If there are multiple solutions, find the rectangle which is closest to (x, y). Here "closest" means the Euclid distance between (x, y) and the center of the rectangle is as small as possible. If there are still multiple solutions, find the lexicographically minimum one. Here "lexicographically minimum" means that we should consider the sub-rectangle as sequence of integers (x_1, y_1, x_2, y_2), so we can choose the lexicographically minimum one.


-----Input-----

The first line contains six integers n, m, x, y, a, b (1 ≤ n, m ≤ 10^9, 0 ≤ x ≤ n, 0 ≤ y ≤ m, 1 ≤ a ≤ n, 1 ≤ b ≤ m).


-----Output-----

Print four integers x_1, y_1, x_2, y_2, which represent the founded sub-rectangle whose left-bottom point is (x_1, y_1) and right-up point is (x_2, y_2).


-----Examples-----
Input
9 9 5 5 2 1

Output
1 3 9 7

Input
100 100 52 50 46 56

Output
17 8 86 92

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Help Vasilisa the Wise 2

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasilisa the Wise from the Kingdom of Far Far Away got a magic box with a secret as a present from her friend Hellawisa the Wise from the Kingdom of A Little Closer. However, Vasilisa the Wise does not know what the box's secret is, since she cannot open it again. She hopes that you will help her one more time with that.

The box's lock looks as follows: it contains 4 identical deepenings for gems as a 2<=×<=2 square, and some integer numbers are written at the lock's edge near the deepenings. The example of a lock is given on the picture below.

The box is accompanied with 9 gems. Their shapes match the deepenings' shapes and each gem contains one number from 1 to 9 (each number is written on exactly one gem). The box will only open after it is decorated with gems correctly: that is, each deepening in the lock should be filled with exactly one gem. Also, the sums of numbers in the square's rows, columns and two diagonals of the square should match the numbers written at the lock's edge. For example, the above lock will open if we fill the deepenings with gems with numbers as is shown on the picture below.

Now Vasilisa the Wise wants to define, given the numbers on the box's lock, which gems she should put in the deepenings to open the box. Help Vasilisa to solve this challenging task.

Input Specification:
The input contains numbers written on the edges of the lock of the box. The first line contains space-separated integers *r*1 and *r*2 that define the required sums of numbers in the rows of the square. The second line contains space-separated integers *c*1 and *c*2 that define the required sums of numbers in the columns of the square. The third line contains space-separated integers *d*1 and *d*2 that define the required sums of numbers on the main and on the side diagonals of the square (1<=≤<=*r*1,<=*r*2,<=*c*1,<=*c*2,<=*d*1,<=*d*2<=≤<=20). Correspondence between the above 6 variables and places where they are written is shown on the picture below. For more clarifications please look at the second sample test that demonstrates the example given in the problem statement.

Output Specification:
Print the scheme of decorating the box with stones: two lines containing two space-separated integers from 1 to 9. The numbers should be pairwise different. If there is no solution for the given lock, then print the single number "-1" (without the quotes).

If there are several solutions, output any.

Demo Input:
['3 7\n4 6\n5 5\n', '11 10\n13 8\n5 16\n', '1 2\n3 4\n5 6\n', '10 10\n10 10\n10 10\n']

Demo Output:
['1 2\n3 4\n', '4 7\n9 1\n', '-1\n', '-1\n']

Note:
Pay attention to the last test from the statement: it is impossible to open the box because for that Vasilisa the Wise would need 4 identical gems containing number "5". However, Vasilisa only has one gem with each number from 1 to 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer n and an array a_1, a_2, …, a_n. You should reorder the elements of the array a in such way that the sum of MEX on prefixes (i-th prefix is a_1, a_2, …, a_i) is maximized.

Formally, you should find an array b_1, b_2, …, b_n, such that the sets of elements of arrays a and b are equal (it is equivalent to array b can be found as an array a with some reordering of its elements) and ∑_{i=1}^{n} MEX(b_1, b_2, …, b_i) is maximized.

MEX of a set of nonnegative integers is the minimal nonnegative integer such that it is not in the set.

For example, MEX(\{1, 2, 3\}) = 0, MEX(\{0, 1, 2, 4, 5\}) = 3.

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 100).

The second line of each test case contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 100).

Output

For each test case print an array b_1, b_2, …, b_n — the optimal reordering of a_1, a_2, …, a_n, so the sum of MEX on its prefixes is maximized.

If there exist multiple optimal answers you can find any.

Example

Input


3
7
4 2 0 1 3 3 7
5
2 2 8 6 9
1
0


Output


0 1 2 3 4 7 3 
2 6 8 9 2 
0 

Note

In the first test case in the answer MEX for prefixes will be: 

  1. MEX(\{0\}) = 1 
  2. MEX(\{0, 1\}) = 2 
  3. MEX(\{0, 1, 2\}) = 3 
  4. MEX(\{0, 1, 2, 3\}) = 4 
  5. MEX(\{0, 1, 2, 3, 4\}) = 5 
  6. MEX(\{0, 1, 2, 3, 4, 7\}) = 5 
  7. MEX(\{0, 1, 2, 3, 4, 7, 3\}) = 5 

The sum of MEX = 1 + 2 + 3 + 4 + 5 + 5 + 5 = 25. It can be proven, that it is a maximum possible sum of MEX on prefixes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of 4 integers  
```[a,b,c,d]``` representing two points ```(a, b)``` and ```(c, d)```, return a string representation of the slope of the line joining these two points. 

For an undefined slope (division by 0), return  ```undefined```  . Note that the "undefined" is case-sensitive.
```
   a:x1
   b:y1
   c:x2
   d:y2
```
   
Assume that ```[a,b,c,d]``` and the answer are all integers 
(no floating numbers!).
Slope:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Whereas humans nowadays read fewer and fewer books on paper, book readership among marmots has surged. Heidi has expanded the library and is now serving longer request sequences.


-----Input-----

Same as the easy version, but the limits have changed: 1 ≤ n, k ≤ 400 000.


-----Output-----

Same as the easy version.


-----Examples-----
Input
4 100
1 2 2 1

Output
2

Input
4 1
1 2 2 1

Output
3

Input
4 2
1 2 3 1

Output
3

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