vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given a rooted tree with $n$ nodes. The nodes are labeled $1$ to $n$, and node $1$ is the root. Each node has a value $v_ i$.

You would like to turn this tree into a heap. That is, you would like to choose the largest possible subset of nodes that satisfy this Heap Property: For every node pair $i$,$j$ in the subset, if node $i$ is an ancestor of node $j$ in the tree, then $v_ i > v_ j$. Note that equality is not allowed.

Figure out the maximum number of nodes you can choose to form such a subset. The subset does not have to form a subtree.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will contain a single integer $n$ ($1 \le n \le 2 \cdot 10^5$), which is the number of nodes in the tree. The nodes are numbered $1$ to $n$.

Each of the next $n$ lines will describe the nodes, in order from $i=1$ to $n$. They will each contain two integers $v_ i$ and $p_ i$, where $v_ i$ ($0 \le v_ i \le 10^9$) is the value in the node, and $p_ i$ ($0 \le p_ i < i$) is the index of its parent. Every node’s index will be strictly greater than its parent node’s index. Only node 1, the root, will have $p_1=0$, since it has no parent. For all other nodes ($i=2, 3, \ldots , n$), $1 \le p_ i < i$.

-----Output-----
Output a single integer representing the number of nodes in the largest subset satisfying the Heap Property.

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

Sample Input 2:
5
4 0
3 1
2 2
1 3
0 4
Sample Output 2:
5

Sample Input 3:
6
3 0
1 1
2 1
3 1
4 1
5 1
Sample Output 3:
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string num representing the digits of a very large integer and an integer k.
You are allowed to swap any two adjacent digits of the integer at most k times.
Return the minimum integer you can obtain also as a string.
 
Example 1:

Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

Example 2:
Input: num = "100", k = 1
Output: "010"
Explanation: It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.

Example 3:
Input: num = "36789", k = 1000
Output: "36789"
Explanation: We can keep the number without any swaps.

Example 4:
Input: num = "22", k = 22
Output: "22"

Example 5:
Input: num = "9438957234785635408", k = 23
Output: "0345989723478563548"

 
Constraints:

1 <= num.length <= 30000
num contains digits only and doesn't have leading zeros.
1 <= k <= 10^9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Have a look at the following numbers.

```
 n | score
---+-------
 1 |  50
 2 |  150
 3 |  300
 4 |  500
 5 |  750
```

Can you find a pattern in it? If so, then write a function `getScore(n)`/`get_score(n)`/`GetScore(n)` which returns the score for any positive number `n`:

```c++
int getScore(1) = return 50;
int getScore(2) = return 150;
int getScore(3) = return 300;
int getScore(4) = return 500;
int getScore(5) = return 750;
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:


       Only the space character ' ' is considered as whitespace character.
       Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.


Example 1:


Input: "42"
Output: 42


Example 2:


Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.


Example 3:


Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.


Example 4:


Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:


Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer, $n$, print the following values for each integer $\boldsymbol{i}$ from $\mbox{1}$ to $n$:

Decimal
Octal
Hexadecimal (capitalized)
Binary

Function Description   

Complete the print_formatted function in the editor below.   

print_formatted has the following parameters:   

int number: the maximum value to print  

Prints   

The four values must be printed on a single line in the order specified above for each $\boldsymbol{i}$ from $\mbox{1}$ to $number$. Each value should be space-padded to match the width of the binary value of $number$ and the values should be separated by a single space.

Input Format

A single integer denoting $n$.

Constraints

$1\leq n\leq99$

Sample Input
17

Sample Output
    1     1     1     1
    2     2     2    10
    3     3     3    11
    4     4     4   100
    5     5     5   101
    6     6     6   110
    7     7     7   111
    8    10     8  1000
    9    11     9  1001
   10    12     A  1010
   11    13     B  1011
   12    14     C  1100
   13    15     D  1101
   14    16     E  1110
   15    17     F  1111
   16    20    10 10000
   17    21    11 10001

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ichihime is the current priestess of the Mahjong Soul Temple. She claims to be human, despite her cat ears.

These days the temple is holding a math contest. Usually, Ichihime lacks interest in these things, but this time the prize for the winner is her favorite — cookies. Ichihime decides to attend the contest. Now she is solving the following problem.[Image] 

You are given four positive integers $a$, $b$, $c$, $d$, such that $a \leq b \leq c \leq d$. 

Your task is to find three integers $x$, $y$, $z$, satisfying the following conditions: $a \leq x \leq b$. $b \leq y \leq c$. $c \leq z \leq d$. There exists a triangle with a positive non-zero area and the lengths of its three sides are $x$, $y$, and $z$.

Ichihime desires to get the cookie, but the problem seems too hard for her. Can you help her?


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 1000$)  — the number of test cases.

The next $t$ lines describe test cases. Each test case is given as four space-separated integers $a$, $b$, $c$, $d$ ($1 \leq a \leq b \leq c \leq d \leq 10^9$).


-----Output-----

For each test case, print three integers $x$, $y$, $z$  — the integers you found satisfying the conditions given in the statement.

It is guaranteed that the answer always exists. If there are multiple answers, print any.


-----Example-----
Input
4
1 3 5 7
1 5 5 7
100000 200000 300000 400000
1 1 977539810 977539810

Output
3 4 5
5 5 5
182690 214748 300999
1 977539810 977539810



-----Note-----

One of the possible solutions to the first test case:

[Image]

One of the possible solutions to the second test case:

[Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a positive integer N.
How many tuples (A,B,C) of positive integers satisfy A \times B + C = N?

-----Constraints-----
 -  2 \leq N \leq 10^6
 - All values in input are integers.

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

-----Output-----
Print the answer.

-----Sample Input-----
3

-----Sample Output-----
3

There are 3 tuples of integers that satisfy A \times B + C = 3: (A, B, C) = (1, 1, 2), (1, 2, 1), (2, 1, 1).

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
An infinitely long railway has a train consisting of *n* cars, numbered from 1 to *n* (the numbers of all the cars are distinct) and positioned in arbitrary order. David Blaine wants to sort the railway cars in the order of increasing numbers. In one move he can make one of the cars disappear from its place and teleport it either to the beginning of the train, or to the end of the train, at his desire. What is the minimum number of actions David Blaine needs to perform in order to sort the train?

Input Specification:
The first line of the input contains integer *n* (1<=≤<=*n*<=≤<=100<=000) — the number of cars in the train. 

The second line contains *n* integers *p**i* (1<=≤<=*p**i*<=≤<=*n*, *p**i*<=≠<=*p**j* if *i*<=≠<=*j*) — the sequence of the numbers of the cars in the train.

Output Specification:
Print a single integer — the minimum number of actions needed to sort the railway cars.

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

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

Note:
In the first sample you need first to teleport the 4-th car, and then the 5-th car to the end of the train.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sayaka Saeki is a member of the student council, which has n other members (excluding Sayaka). The i-th member has a height of a_i millimeters.

It's the end of the school year and Sayaka wants to take a picture of all other members of the student council. Being the hard-working and perfectionist girl as she is, she wants to arrange all the members in a line such that the amount of photogenic consecutive pairs of members is as large as possible.

A pair of two consecutive members u and v on a line is considered photogenic if their average height is an integer, i.e. (a_u + a_v)/(2) is an integer.

Help Sayaka arrange the other members to maximize the number of photogenic consecutive pairs.

Input

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

The first line of each test case contains a single integer n (2 ≤ n ≤ 2000) — the number of other council members.

The second line of each test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 2 ⋅ 10^5) — the heights of each of the other members in millimeters.

It is guaranteed that the sum of n over all test cases does not exceed 2000.

Output

For each test case, output on one line n integers representing the heights of the other members in the order, which gives the largest number of photogenic consecutive pairs. If there are multiple such orders, output any of them.

Example

Input


4
3
1 1 2
3
1 1 1
8
10 9 13 15 3 16 9 13
2
18 9


Output


1 1 2 
1 1 1 
13 9 13 15 3 9 16 10 
9 18 

Note

In the first test case, there is one photogenic pair: (1, 1) is photogenic, as (1+1)/(2)=1 is integer, while (1, 2) isn't, as (1+2)/(2)=1.5 isn't integer.

In the second test case, both pairs are photogenic.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice is driving from her home to her office which is A kilometers away and will take her X hours to reach.  
Bob is driving from his home to his office which is B kilometers away and will take him Y hours to reach.

Determine who is driving faster, else, if they are both driving at the same speed print EQUAL.

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

- The first line will contain T, the number of test cases. Then the test cases follow.
- Each test case consists of a single line of input, containing four integers A,X,B, and Y, the distances and and the times taken by Alice and Bob respectively.

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

For each test case, if Alice is faster, print ALICE. Else if Bob is faster, print BOB. If both are equal, print EQUAL.

You may print each character of the string in uppercase or lowercase (for example, the strings equal, equAL, EquAl, and EQUAL will all be treated as identical).

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

$1 ≤ T ≤ 1000$
$1 ≤ A,X,B,Y ≤ 1000$

----- Sample Input 1 ------ 
3
20 6 20 5
10 3 20 6
9 1 1 1

----- Sample Output 1 ------ 
Bob
Equal
Alice

----- explanation 1 ------ 
Test case $1$: Since Bob travels the distance between his office and house in $5$ hours, whereas Alice travels the same distance of $20$ kms in $6$ hours, BOB is faster.

Test case $2$: Since Alice travels the distance of $10$ km between her office and house in $3$ hours and Bob travels a distance of $20$ km in $6$ hours, they have equal speeds.

Test case $3$: Since Alice travels the distance of $9$ km between her office and house in $1$ hour and Bob travels only a distance of $1$ km in the same time, ALICE is faster.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
DevuLand is a very strange place. There are n villages in it. Some of the villages are occupied by dinosaurs while the remaining ones by villagers.
	You are given the information of DevuLand 
	by an array D of size n. If D[i] is non-negative, it means that there are D[i] villagers in that village. 
	Otherwise, it means that are -D[i] 
	dinosaurs in that village.

	It is also guaranteed that total number of villagers in DevuLand is equal to total number of dinosaurs.

Once dinosaurs got very hungry and started eating villagers. Frightened villagers gathered immediately and met their Sarpanch Deviji. Deviji, being a very daring and negotiable person, met to the head
of dinosaurs. Soon both parties called a truce. It was decided that the villagers will provide laddus to 
the dinosaurs. So everyday, each villager will take exactly one laddu to one of the dinosaurs in such a way that no dinosaur remains hungry (note that this is possible because number of villagers is the same as the number of dinosaurs).

Actually, carrying laddus is a quite a tough job. Villagers have to use a bullock cart for that. It takes one unit of grass a bullock to 
carry a cart with 1 laddu for 1 kilometre. Laddus used to be very heavy in DevuLand, so a bullock cart can not carry more than one laddu.

It is also given distance between village indexed i and j is |j - i| (the absolute value) kilometres.

Now villagers sat down and found a strategy to feed laddus to dinosaurs so that they need to buy the least amount of grass from the nearby market. 
They are not very good in 
calculations, please find out what is the minimum number of units of grass they need to buy.

-----Input-----

First line of the input contains an integer T denoting number of test cases.

For each test case, there are two lines. 

First line contains a single integer denoting n: number of villages. 

Second line contains n space separated integers denoting the array D.

-----Output-----

For each test case, print a single line containing the integer corresponding to answer of the problem.

-----Constraints-----

-  1 ≤ T ≤ 10^5 
-  1 ≤ n ≤ 10^5 
-  -10^4 ≤ D[i] ≤ 10^4 
-  Sum of n over all the test cases will be ≤ 10^6 
-  It is guaranteed that sum of D[i] is zero for a single test case which ensures that there are equal number of villagers and dinosaurs. 

-----Example-----
Input:
3
2
5 -5
2
-5 5
3
1 2 -3
Output:
5
5
4

-----Explanation-----
Example case 1. Each villager in village 1, need to walk 1 km to reach to the dinosaur in 2nd village.
Example case 2. Each villager in village 2, need to walk 1 km to reach to the dinosaur 1st village.
Example case 3. Each villager in village 1, need to walk 2 km to reach to the dinosaur in 3rd village whereas Each villager in village 2, 
need to walk 1 km to reach to the dinosaur in 3rd village.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Generate and return **all** possible increasing arithmetic progressions of six primes `[a, b, c, d, e, f]` between the given limits. Note: the upper and lower limits are inclusive.

An arithmetic progression is a sequence where the difference between consecutive numbers is the same, such as: 2, 4, 6, 8.

A prime number is a number that is divisible only by itself and 1 (e.g. 2, 3, 5, 7, 11)

Your solutions should be returned as lists inside a list in ascending order of the first item (if there are multiple lists with same first item, return in ascending order for the second item etc) are the e.g: `[ [a, b, c, d, e, f], [g, h, i, j, k, l] ]` where `a < g`. If there are no solutions, return an empty list: `[]`

## Examples

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a singly linked list, your task is to remove every k^{th} node from the linked list.
Input:
The first line of input contains number of test cases T. Then T test cases follow. Every test case contains 3 lines. First line of every test case contains an integer N denoting the size of the linked list . The second line contains N space separated values of the linked list. The third line contains an integer K.
Output:
Output for each test case will be space separated values of the nodes of the new transformed linked list.
User Task:
The task is to complete the function deleteK() which should delete every kth nodes from the linked list.
Constraints:
1 <= T <= 50
1 <= N <= 100
1 <= element of linked list <= 1000
0 <= k <= 100
Example:
Input:
2
8
1 2 3 4 5 6 7 8
3
4
1 2 3 4
2
Output:
1 2 4 5 7 8
1 3
Explanation:
Testcase 1: After removing every 3rd element from the linked list, we have updated list as 1, 2, 4, 5, 7 and 8, and the elements which are removed are 3 and 6.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The administration of the Tomsk Region firmly believes that it's time to become a megacity (that is, get population of one million). Instead of improving the demographic situation, they decided to achieve its goal by expanding the boundaries of the city.

The city of Tomsk can be represented as point on the plane with coordinates (0; 0). The city is surrounded with *n* other locations, the *i*-th one has coordinates (*x**i*, *y**i*) with the population of *k**i* people. You can widen the city boundaries to a circle of radius *r*. In such case all locations inside the circle and on its border are included into the city.

Your goal is to write a program that will determine the minimum radius *r*, to which is necessary to expand the boundaries of Tomsk, so that it becomes a megacity.

Input Specification:
The first line of the input contains two integers *n* and *s* (1<=≤<=*n*<=≤<=103; 1<=≤<=*s*<=&lt;<=106) — the number of locatons around Tomsk city and the population of the city. Then *n* lines follow. The *i*-th line contains three integers — the *x**i* and *y**i* coordinate values of the *i*-th location and the number *k**i* of people in it (1<=≤<=*k**i*<=&lt;<=106). Each coordinate is an integer and doesn't exceed 104 in its absolute value.

It is guaranteed that no two locations are at the same point and no location is at point (0; 0).

Output Specification:
In the output, print "-1" (without the quotes), if Tomsk won't be able to become a megacity. Otherwise, in the first line print a single real number — the minimum radius of the circle that the city needs to expand to in order to become a megacity.

The answer is considered correct if the absolute or relative error don't exceed 10<=-<=6.

Demo Input:
['4 999998\n1 1 1\n2 2 1\n3 3 1\n2 -2 1\n', '4 999998\n1 1 2\n2 2 1\n3 3 1\n2 -2 1\n', '2 1\n1 1 999997\n2 2 1\n']

Demo Output:
['2.8284271\n', '1.4142136\n', '-1']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You will be given the prime factors of a number as an array.
E.g: ```[2,2,2,3,3,5,5,13]```

You need to find the number, n, to which that prime factorization belongs.
It will be:
```
n = 2³.3².5².13 = 23400
```
Then, generate the divisors of this number.

Your function ```get_num() or getNum()``` will receive an array with potentially unordered prime factors and should output: an array with the found integer n at index 0, the amount of total divisors (both prime and compound numbers) at index 1, followed the smallest factor (index 2, and the biggest one (last element)

We will see the example given above with the only difference that the array of the prime factors is unordered.

The list of divisors for that number (23400) is:
```
2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 15, 18, 20, 24, 25, 26, 30, 36, 39, 40, 45, 50, 52, 60, 65, 72, 75, 78, 90, 100, 104, 117, 120, 130, 150, 156, 180, 195, 200, 225, 234, 260, 300, 312, 325, 360, 390, 450, 468, 520, 585, 600, 650, 780, 900, 936, 975, 1170, 1300, 1560, 1800, 1950, 2340, 2600, 2925, 3900, 4680, 5850, 7800, 11700 (not considering the integer 23400 itself)
```
There is a total amount of ```71``` divisors. The smallest divisor is ```2``` and the highest ```11700```.
So the expected output will be: 
```
get_num([2,13,2,5,2,5,3,3]) == [23400, 71, 2, 11700]
```
Enjoy!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The final round of Bayan Programming Contest will be held in Tehran, and the participants will be carried around with a yellow bus. The bus has 34 passenger seats: 4 seats in the last row and 3 seats in remaining rows.  [Image] 

The event coordinator has a list of k participants who should be picked up at the airport. When a participant gets on the bus, he will sit in the last row with an empty seat. If there is more than one empty seat in that row, he will take the leftmost one. 

In order to keep track of the people who are on the bus, the event coordinator needs a figure showing which seats are going to be taken by k participants. Your task is to draw the figure representing occupied seats.


-----Input-----

The only line of input contains integer k, (0 ≤ k ≤ 34), denoting the number of participants.


-----Output-----

Print the figure of a bus with k passengers as described in sample tests. Character '#' denotes an empty seat, while 'O' denotes a taken seat. 'D' is the bus driver and other characters in the output are for the purpose of beautifying the figure. Strictly follow the sample test cases output format. Print exactly six lines. Do not output extra space or other characters.


-----Examples-----
Input
9

Output
+------------------------+
|O.O.O.#.#.#.#.#.#.#.#.|D|)
|O.O.O.#.#.#.#.#.#.#.#.|.|
|O.......................|
|O.O.#.#.#.#.#.#.#.#.#.|.|)
+------------------------+

Input
20

Output
+------------------------+
|O.O.O.O.O.O.O.#.#.#.#.|D|)
|O.O.O.O.O.O.#.#.#.#.#.|.|
|O.......................|
|O.O.O.O.O.O.#.#.#.#.#.|.|)
+------------------------+

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