vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Yulia works for a metal processing plant in Ekaterinburg. This plant processes ores mined in the Ural mountains, extracting precious metals such as chalcopyrite, platinum and gold from the ores. Every month the plant receives $n$ shipments of unprocessed ore. Yulia needs to partition these shipments into two groups based on their similarity. Then, each group is sent to one of two ore processing buildings of the plant.

To perform this partitioning, Yulia first calculates a numeric distance $d(i, j)$ for each pair of shipments $1 \le i \le n$ and $1 \le j \le n$, where the smaller the distance, the more similar the shipments $i$ and $j$ are. For a subset $S \subseteq \{ 1, \ldots , n\} $ of shipments, she then defines the disparity$D$ of $S$ as the maximum distance between a pair of shipments in the subset, that is,\[ D(S) = \max _{i, j \in S} d(i, j). \]

Yulia then partitions the shipments into two subsets $A$ and $B$ in such a way that the sum of their disparities $D(A) + D(B)$ is minimized. Your task is to help her find this partitioning.

-----Input-----
The input consists of a single test case. The first line contains an integer $n$ ($1 \le n \le 200$) indicating the number of shipments. The following $n - 1$ lines contain the distances $d(i,j)$. The $i^{th}$ of these lines contains $n - i$ integers and the $j^{th}$ integer of that line gives the value of $d(i, i+j)$. The distances are symmetric, so $d(j, i) = d(i, j)$, and the distance of a shipment to itself is $0$. All distances are integers between $0$ and $10^9$ (inclusive).

-----Output-----
Display the minimum possible sum of disparities for partitioning the shipments into two groups.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Alyona and a tree

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Alyona has a tree with *n* vertices. The root of the tree is the vertex 1. In each vertex Alyona wrote an positive integer, in the vertex *i* she wrote *a**i*. Moreover, the girl wrote a positive integer to every edge of the tree (possibly, different integers on different edges).

Let's define *dist*(*v*,<=*u*) as the sum of the integers written on the edges of the simple path from *v* to *u*.

The vertex *v* controls the vertex *u* (*v*<=≠<=*u*) if and only if *u* is in the subtree of *v* and *dist*(*v*,<=*u*)<=≤<=*a**u*.

Alyona wants to settle in some vertex. In order to do this, she wants to know for each vertex *v* what is the number of vertices *u* such that *v* controls *u*.

Input Specification:
The first line contains single integer *n* (1<=≤<=*n*<=≤<=2·105).

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109) — the integers written in the vertices.

The next (*n*<=-<=1) lines contain two integers each. The *i*-th of these lines contains integers *p**i* and *w**i* (1<=≤<=*p**i*<=≤<=*n*, 1<=≤<=*w**i*<=≤<=109) — the parent of the (*i*<=+<=1)-th vertex in the tree and the number written on the edge between *p**i* and (*i*<=+<=1).

It is guaranteed that the given graph is a tree.

Output Specification:
Print *n* integers — the *i*-th of these numbers should be equal to the number of vertices that the *i*-th vertex controls.

Demo Input:
['5\n2 5 1 4 6\n1 7\n1 1\n3 5\n3 6\n', '5\n9 7 8 6 5\n1 1\n2 1\n3 1\n4 1\n']

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

Note:
In the example test case the vertex 1 controls the vertex 3, the vertex 3 controls the vertex 5 (note that is doesn't mean the vertex 1 controls the vertex 5).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n digital panels placed in a straight line. Each panel can show any digit from 0 to 9. Initially, all panels show 0.

Every second, the digit shown by each panel increases by 1. In other words, at the end of every second, a panel that showed 9 would now show 0, a panel that showed 0 would now show 1, a panel that showed 1 would now show 2, and so on.

When a panel is paused, the digit displayed on the panel does not change in the subsequent seconds.

You must pause exactly one of these panels, at any second you wish. Then, the panels adjacent to it get paused one second later, the panels adjacent to those get paused 2 seconds later, and so on. In other words, if you pause panel x, panel y (for all valid y) would be paused exactly |x−y| seconds later.

For example, suppose there are 4 panels, and the 3-rd panel is paused when the digit 9 is on it.

  * The panel 1 pauses 2 seconds later, so it has the digit 1; 
  * the panel 2 pauses 1 second later, so it has the digit 0; 
  * the panel 4 pauses 1 second later, so it has the digit 0. 



The resulting 4-digit number is 1090. Note that this example is not optimal for n = 4.

Once all panels have been paused, you write the digits displayed on them from left to right, to form an n digit number (it can consist of leading zeros). What is the largest possible number you can get? Initially, all panels show 0.

Input

The first line of the input contains a single integer t (1 ≤ t ≤ 100) — the number of test cases. Each test case consists of a single line containing a single integer n (1 ≤ n ≤ 2⋅10^5).

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

Output

For each test case, print the largest number you can achieve, if you pause one panel optimally.

Example

Input


2
1
2


Output


9
98

Note

In the first test case, it is optimal to pause the first panel when the number 9 is displayed on it.

In the second test case, it is optimal to pause the second panel when the number 8 is displayed on it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n+2 people sitting in a line, numbered from 0 to n+1. Some K distinct people with numbers ranging between 1 and n (inclusive) have letters given to them. The role of people with letters is to give their letters to one person sitting adjacent to them. At the end of this procedure, let X denote the sum of the numbers of all the people who have letters.  Find the number of possible ways that X can equal a given number, T, modulo 10^9 + 7. 

Note, if a person has two letters, count him/her twice.

Input:

The first line contains three integers, N, K, and T, in that order. 

Next line consists of K integers, the numbers of the people who have letters. 

Output:

Output the answer to the problem.

Constraints:

1 ≤ N ≤ 2000
1 ≤ K ≤ 2000
1 ≤ T ≤ 4000000
1 ≤ Number of everyone who has a letter ≤ N

SAMPLE INPUT
3 1 1
2

SAMPLE OUTPUT
1

Explanation

In order for this to work, person 2 must pass the letter to person 1.  So, there is exactly 1 way.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya and Vasya decided to play a game. They have *n* cards (*n* is an even number). A single integer is written on each card.

Before the game Petya will choose an integer and after that Vasya will choose another integer (different from the number that Petya chose). During the game each player takes all the cards with number he chose. For example, if Petya chose number 5 before the game he will take all cards on which 5 is written and if Vasya chose number 10 before the game he will take all cards on which 10 is written.

The game is considered fair if Petya and Vasya can take all *n* cards, and the number of cards each player gets is the same.

Determine whether Petya and Vasya can choose integer numbers before the game so that the game is fair.

Input Specification:
The first line contains a single integer *n* (2<=≤<=*n*<=≤<=100) — number of cards. It is guaranteed that *n* is an even number.

The following *n* lines contain a sequence of integers *a*1,<=*a*2,<=...,<=*a**n* (one integer per line, 1<=≤<=*a**i*<=≤<=100) — numbers written on the *n* cards.

Output Specification:
If it is impossible for Petya and Vasya to choose numbers in such a way that the game will be fair, print "NO" (without quotes) in the first line. In this case you should not print anything more.

In the other case print "YES" (without quotes) in the first line. In the second line print two distinct integers — number that Petya should choose and the number that Vasya should choose to make the game fair. If there are several solutions, print any of them.

Demo Input:
['4\n11\n27\n27\n11\n', '2\n6\n6\n', '6\n10\n20\n30\n20\n10\n20\n', '6\n1\n1\n2\n2\n3\n3\n']

Demo Output:
['YES\n11 27\n', 'NO\n', 'NO\n', 'NO\n']

Note:
In the first example the game will be fair if, for example, Petya chooses number 11, and Vasya chooses number 27. Then the will take all cards — Petya will take cards 1 and 4, and Vasya will take cards 2 and 3. Thus, each of them will take exactly two cards.

In the second example fair game is impossible because the numbers written on the cards are equal, but the numbers that Petya and Vasya should choose should be distinct.

In the third example it is impossible to take all cards. Petya and Vasya can take at most five cards — for example, Petya can choose number 10 and Vasya can choose number 20. But for the game to be fair it is necessary to take 6 cards.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anadi has a set of dominoes. Every domino has two parts, and each part contains some dots. For every $a$ and $b$ such that $1 \leq a \leq b \leq 6$, there is exactly one domino with $a$ dots on one half and $b$ dots on the other half. The set contains exactly $21$ dominoes. Here is an exact illustration of his set:

 [Image] 

Also, Anadi has an undirected graph without self-loops and multiple edges. He wants to choose some dominoes and place them on the edges of this graph. He can use at most one domino of each type. Each edge can fit at most one domino. It's not necessary to place a domino on each edge of the graph.

When placing a domino on an edge, he also chooses its direction. In other words, one half of any placed domino must be directed toward one of the endpoints of the edge and the other half must be directed toward the other endpoint. There's a catch: if there are multiple halves of dominoes directed toward the same vertex, each of these halves must contain the same number of dots.

How many dominoes at most can Anadi place on the edges of his graph?


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 7$, $0 \leq m \leq \frac{n\cdot(n-1)}{2}$) — the number of vertices and the number of edges in the graph.

The next $m$ lines contain two integers each. Integers in the $i$-th line are $a_i$ and $b_i$ ($1 \leq a, b \leq n$, $a \neq b$) and denote that there is an edge which connects vertices $a_i$ and $b_i$.

The graph might be disconnected. It's however guaranteed that the graph doesn't contain any self-loops, and that there is at most one edge between any pair of vertices.


-----Output-----

Output one integer which denotes the maximum number of dominoes which Anadi can place on the edges of the graph.


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

Output
4

Input
7 0

Output
0

Input
3 1
1 3

Output
1

Input
7 21
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7

Output
16



-----Note-----

Here is an illustration of Anadi's graph from the first sample test:

 [Image] 

And here is one of the ways to place a domino on each of its edges:

 [Image] 

Note that each vertex is faced by the halves of dominoes with the same number of dots. For instance, all halves directed toward vertex $1$ have three dots.

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

He defines the *subsequence-number* of a non-empty [subsequence] 
S of array A as the number formed by the concatenation of all the elements of the subsequence S. 

Find the count of non-empty subsequences of A having their *subsequence-numbers* divisible by 7. Since the answer can be huge, output it modulo 10^{9} + 7.

For example: Consider A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. A subsequence S of A is [2, 5, 7, 10]. The *subsequence-number* of this subsequence is 25710.

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

- The first line will contain T, the number of test cases. Then the test cases follow.
- The first line of each test case contains one integer N, the size of the array.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} — the elements of the array A.

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

For each test case, output in a single line the number of subsequences with *subsequence-number* divisible by 7 modulo 1000000007.

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

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

----- Sample Input 1 ------ 
3
2
1 2
4
1 2 3 4
2
7 7

----- Sample Output 1 ------ 
0
1
3

----- explanation 1 ------ 
Test case $1$: Only $3$ subsequences are possible for the given array. These are $[1]$, $[1, 2]$, and $[2]$. The *subsequence-numbers* are $1$, $12$, and $2$ respectively. None of the *subsequence-numbers* are divisible by $7$, so the answer is $0$.

Test case $2$: $[1, 4]$ is the only subsequence having its *subsequence-number* $14$ which is divisible by $7$. So, the answer is $1$.

Test case $3$: All the non-empty subsequences $[7]$, $[7]$, and $[7, 7]$ have their *subsequence-numbers* $7, 7,$ and $77$ divisible by $7$. So, the answer is $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given integers N and D. Find N positive integers x1...xN such that the difference of their product and their sum equals D.

Input

The only line of input contains integers N (2 ≤ N ≤ 1000) and D (0 ≤ D ≤ 1000).

Output

Output N integers that satisfy the given condition in non-decreasing order (in a single line, separated with spaces). Note that some numbers can be equal. Numbers printed by you must not exceed 106.

Examples

Input

2 1


Output

2 3


Input

3 5


Output

1 2 8

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ilya got tired of sports programming, left university and got a job in the subway. He was given the task to determine the escalator load factor. 

Let's assume that *n* people stand in the queue for the escalator. At each second one of the two following possibilities takes place: either the first person in the queue enters the escalator with probability *p*, or the first person in the queue doesn't move with probability (1<=-<=*p*), paralyzed by his fear of escalators and making the whole queue wait behind him.

Formally speaking, the *i*-th person in the queue cannot enter the escalator until people with indices from 1 to *i*<=-<=1 inclusive enter it. In one second only one person can enter the escalator. The escalator is infinite, so if a person enters it, he never leaves it, that is he will be standing on the escalator at any following second. Ilya needs to count the expected value of the number of people standing on the escalator after *t* seconds. 

Your task is to help him solve this complicated task.

Input Specification:
The first line of the input contains three numbers *n*,<=*p*,<=*t* (1<=≤<=*n*,<=*t*<=≤<=2000, 0<=≤<=*p*<=≤<=1). Numbers *n* and *t* are integers, number *p* is real, given with exactly two digits after the decimal point.

Output Specification:
Print a single real number — the expected number of people who will be standing on the escalator after *t* seconds. The absolute or relative error mustn't exceed 10<=-<=6.

Demo Input:
['1 0.50 1\n', '1 0.50 4\n', '4 0.20 2\n']

Demo Output:
['0.5\n', '0.9375\n', '0.4\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi received otoshidama (New Year's money gifts) from N of his relatives.
You are given N values x_1, x_2, ..., x_N and N strings u_1, u_2, ..., u_N as input. Each string u_i is either JPY or BTC, and x_i and u_i represent the content of the otoshidama from the i-th relative.
For example, if x_1 = 10000 and u_1 = JPY, the otoshidama from the first relative is 10000 Japanese yen; if x_2 = 0.10000000 and u_2 = BTC, the otoshidama from the second relative is 0.1 bitcoins.
If we convert the bitcoins into yen at the rate of 380000.0 JPY per 1.0 BTC, how much are the gifts worth in total?

-----Constraints-----
 - 2 \leq N \leq 10
 - u_i = JPY or BTC.
 - If u_i = JPY, x_i is an integer such that 1 \leq x_i \leq 10^8.
 - If u_i = BTC, x_i is a decimal with 8 decimal digits, such that 0.00000001 \leq x_i \leq 100.00000000.

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 u_1
x_2 u_2
:
x_N u_N

-----Output-----
If the gifts are worth Y yen in total, print the value Y (not necessarily an integer).
Output will be judged correct when the absolute or relative error from the judge's output is at most 10^{-5}.

-----Sample Input-----
2
10000 JPY
0.10000000 BTC

-----Sample Output-----
48000.0

The otoshidama from the first relative is 10000 yen. The otoshidama from the second relative is 0.1 bitcoins, which is worth 38000.0 yen if converted at the rate of 380000.0 JPY per 1.0 BTC. The sum of these is 48000.0 yen.
Outputs such as 48000 and 48000.1 will also be judged correct.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya and Kolya play a game with a string, using the following rules. Initially, Kolya creates a string *s*, consisting of small English letters, and uniformly at random chooses an integer *k* from a segment [0,<=*len*(*s*)<=-<=1]. He tells Vasya this string *s*, and then shifts it *k* letters to the left, i. e. creates a new string *t*<==<=*s**k*<=+<=1*s**k*<=+<=2... *s**n**s*1*s*2... *s**k*. Vasya does not know the integer *k* nor the string *t*, but he wants to guess the integer *k*. To do this, he asks Kolya to tell him the first letter of the new string, and then, after he sees it, open one more letter on some position, which Vasya can choose.

Vasya understands, that he can't guarantee that he will win, but he wants to know the probability of winning, if he plays optimally. He wants you to compute this probability. 

Note that Vasya wants to know the value of *k* uniquely, it means, that if there are at least two cyclic shifts of *s* that fit the information Vasya knowns, Vasya loses. Of course, at any moment of the game Vasya wants to maximize the probability of his win.

Input Specification:
The only string contains the string *s* of length *l* (3<=≤<=*l*<=≤<=5000), consisting of small English letters only.

Output Specification:
Print the only number — the answer for the problem. You answer is considered correct, if its absolute or relative error does not exceed 10<=-<=6.

Formally, let your answer be *a*, and the jury's answer be *b*. Your answer is considered correct if 

Demo Input:
['technocup\n', 'tictictactac\n', 'bbaabaabbb\n']

Demo Output:
['1.000000000000000\n', '0.333333333333333\n', '0.100000000000000\n']

Note:
In the first example Vasya can always open the second letter after opening the first letter, and the cyclic shift is always determined uniquely.

In the second example if the first opened letter of *t* is "t" or "c", then Vasya can't guess the shift by opening only one other letter. On the other hand, if the first letter is "i" or "a", then he can open the fourth letter and determine the shift uniquely.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Vasya decided to improve his pistol shooting skills. Today his coach offered him the following exercise. He placed $n$ cans in a row on a table. Cans are numbered from left to right from $1$ to $n$. Vasya has to knock down each can exactly once to finish the exercise. He is allowed to choose the order in which he will knock the cans down.

Vasya knows that the durability of the $i$-th can is $a_i$. It means that if Vasya has already knocked $x$ cans down and is now about to start shooting the $i$-th one, he will need $(a_i \cdot x + 1)$ shots to knock it down. You can assume that if Vasya starts shooting the $i$-th can, he will be shooting it until he knocks it down.

Your task is to choose such an order of shooting so that the number of shots required to knock each of the $n$ given cans down exactly once is minimum possible.


-----Input-----

The first line of the input contains one integer $n$ $(2 \le n \le 1\,000)$ — the number of cans.

The second line of the input contains the sequence $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 1\,000)$, where $a_i$ is the durability of the $i$-th can.


-----Output-----

In the first line print the minimum number of shots required to knock each of the $n$ given cans down exactly once.

In the second line print the sequence consisting of $n$ distinct integers from $1$ to $n$ — the order of indices of cans that minimizes the number of shots required. If there are several answers, you can print any of them.


-----Examples-----
Input
3
20 10 20

Output
43
1 3 2 

Input
4
10 10 10 10

Output
64
2 1 4 3 

Input
6
5 4 5 4 4 5

Output
69
6 1 3 5 2 4 

Input
2
1 4

Output
3
2 1 



-----Note-----

In the first example Vasya can start shooting from the first can. He knocks it down with the first shot because he haven't knocked any other cans down before. After that he has to shoot the third can. To knock it down he shoots $20 \cdot 1 + 1 = 21$ times. After that only second can remains. To knock it down Vasya shoots $10 \cdot 2 + 1 = 21$ times. So the total number of shots is $1 + 21 + 21 = 43$.

In the second example the order of shooting does not matter because all cans have the same durability.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a set of distinct integers, print the size of a maximal subset of $S$ where the sum of any $2$ numbers in $\text{S'}$ is not evenly divisible by $k$.

Example 

$S=[19,10,12,10,24,25,22]$ $k=4$

One of the arrays that can be created is $S'[0]=[10,12,25]$.  Another is $S'[1]=[19,22,24]$.  After testing all permutations, the maximum length solution array has $3$ elements.  

Function Description  

Complete the nonDivisibleSubset function in the editor below.  

nonDivisibleSubset has the following parameter(s):  

int S[n]: an array of integers  
int k: the divisor  

Returns   

int: the length of the longest subset of $S$ meeting the criteria  

Input Format

The first line contains $2$ space-separated integers, $n$ and $k$, the number of values in $S$ and the non factor. 

The second line contains $n$ space-separated integers, each an $S[i]$, the unique values of the set.

Constraints

$1 \leq n \leq 10^5$
$1 \le k \le100$
$1\leq S[i]\leq10^{9}$
All of the given numbers are distinct.

Sample Input
STDIN    Function
-----    --------
4 3      S[] size n = 4, k = 3
1 7 2 4  S = [1, 7, 2, 4]

Sample Output
3

Explanation

The sums of all permutations of two elements from $S=\{1,7,2,4\}$ are:

1 + 7 = 8
1 + 2 = 3
1 + 4 = 5
7 + 2 = 9
7 + 4 = 11
2 + 4 = 6

Only $S'=\{1,7,4\}$ will not ever sum to a multiple of $k=3$.

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