vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The image shows how we can obtain the Harmonic Conjugated Point of three aligned points A, B, C.

- We choose any point L, that is not in the line with A, B and C. We form the triangle ABL

- Then we draw a line from point C that intersects the sides of this triangle at points M and N respectively.

- We draw the diagonals of the quadrilateral ABNM; they are AN and BM and they intersect at point K

- We unit, with a line L and K, and this line intersects the line of points A, B and C at point D

The point D is named the Conjugated Harmonic Point of the points A, B, C.
You can get more knowledge related with this point at: (https://en.wikipedia.org/wiki/Projective_harmonic_conjugate)

If we apply the theorems of Ceva (https://en.wikipedia.org/wiki/Ceva%27s_theorem)
and Menelaus (https://en.wikipedia.org/wiki/Menelaus%27_theorem) we will have this formula:



AC, in the above formula is the length of the segment of points A to C in this direction and its value is:

```AC = xA - xC```

Transform the above formula using the coordinates ```xA, xB, xC and xD```

The task is to create a function ```harmon_pointTrip()```, that receives three arguments, the coordinates of points xA, xB and xC, with values such that : ```xA < xB < xC```, this function should output the coordinates of point D for each given triplet, such that

`xA < xD < xB < xC`, or to be clearer

let's see some cases:
```python
harmon_pointTrip(xA, xB, xC) ------> xD # the result should be expressed up to four decimals (rounded result)
harmon_pointTrip(2, 10, 20) -----> 7.1429 # (2 < 7.1429 < 10 < 20, satisfies the constraint)
harmon_pointTrip(3, 9, 18) -----> 6.75
```


Enjoy it and happy coding!!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a string of length n+1 of characters 'A' and 'B'. The first character and last character of the string are equal to 'A'.

You are given m indices p_1, p_2, …, p_m (0-indexation) denoting the other indices of characters 'A' in the string.

Let's denote the minimum distance between two neighboring 'A' as l, and maximum distance between neighboring 'A' as r.

For example, (l,r) of string "ABBAABBBA" is (1,4).

And let's denote the balance degree of a string as the value of r-l.

Now Dreamoon wants to change exactly k characters from 'B' to 'A', and he wants to make the balance degree of the string as small as possible.

Please calculate the required minimum possible value of balance degree.

Input

The first line contains one integer t denoting the number of test cases (1 ≤ t ≤ 400 000).

For each test case, the first line contains three integers n, m and k (1 ≤ n ≤ 10^{15}, 0 ≤ m ≤ 400 000, 0 ≤ k < n - m).

The second line contains m integers p_1, p_2, …, p_m, (0 < p_1 < p_2 < … < p_m < n).

The total sum of m is at most 400 000.

Output

For each test case, print one integer: the smallest possible value of balance degree after k changes of 'B' to 'A'.

Example

Input


5
80 3 5
11 24 50
81 7 12
4 10 17 26 37 48 61
25 10 14
3 4 7 12 13 15 17 19 21 23
1 0 0

10 2 0
2 4


Output


5
2
0
0
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An IT company is working on a large project. The project is broken into N modules and distributed to different teams. Each team can work parallelly. The amount of time (in months) required to complete each module is given in an array duration[ ] i.e. time needed to complete i^{th} module is duration[i] months. 
You are also given M dependencies such that for each i (1 ≤ i ≤ M)  dependencies[i][1]^{th} module can be started after dependencies[i][0]^{th} module is completed.
As the project manager, compute the minimum time required to complete the project.
Note: It is guaranteed that a module is not dependent on itself.
Example 1:
Input:
N = 6, M = 6
duration[] = {1, 2, 3, 1, 3, 2}
dependencies[][]:
[[5, 2]
 [5, 0]
 [4, 0] 
 [4, 1]
 [2, 3]
 [3, 1]]
Output: 
8
Explanation: 
The Graph of dependency forms this and 
the project will be completed when Module 
1 is completed which takes 8 months.
Example 2:
Input:
N = 3, M = 3
duration[] = {5, 5, 5}
dependencies[][]:
[[0, 1]
 [1, 2]
 [2, 0]]
Output: 
-1
Explanation: 
There is a cycle in the dependency graph 
hence the project cannot be completed.
Your Task:
Complete the function minTime() which takes N, M, duration array, and dependencies array as input parameter and return the minimum time required. return -1 if the project can not be completed. 
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ M ≤ 2*10^{5}
0 ≤ duration[i] ≤ 10^{5}
0 ≤ dependencies[i][j] < N

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Genos needs your help. He was asked to solve the following programming problem by Saitama:

The length of some string *s* is denoted |*s*|. The Hamming distance between two strings *s* and *t* of equal length is defined as , where *s**i* is the *i*-th character of *s* and *t**i* is the *i*-th character of *t*. For example, the Hamming distance between string "0011" and string "0110" is |0<=-<=0|<=+<=|0<=-<=1|<=+<=|1<=-<=1|<=+<=|1<=-<=0|<==<=0<=+<=1<=+<=0<=+<=1<==<=2.

Given two binary strings *a* and *b*, find the sum of the Hamming distances between *a* and all contiguous substrings of *b* of length |*a*|.

Input Specification:
The first line of the input contains binary string *a* (1<=≤<=|*a*|<=≤<=200<=000).

The second line of the input contains binary string *b* (|*a*|<=≤<=|*b*|<=≤<=200<=000).

Both strings are guaranteed to consist of characters '0' and '1' only.

Output Specification:
Print a single integer — the sum of Hamming distances between *a* and all contiguous substrings of *b* of length |*a*|.

Demo Input:
['01\n00111\n', '0011\n0110\n']

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

Note:
For the first sample case, there are four contiguous substrings of *b* of length |*a*|: "00", "01", "11", and "11". The distance between "01" and "00" is |0 - 0| + |1 - 0| = 1. The distance between "01" and "01" is |0 - 0| + |1 - 1| = 0. The distance between "01" and "11" is |0 - 1| + |1 - 1| = 1. Last distance counts twice, as there are two occurrences of string "11". The sum of these edit distances is 1 + 0 + 1 + 1 = 3.

The second sample case is described in the statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This program tests the life of an
evaporator containing a gas. 

We know the content of the evaporator (content in ml),
the percentage of foam or gas lost every day (evap_per_day)
and the threshold (threshold) in percentage beyond which
the evaporator is no longer useful.
All numbers are strictly positive.

The program reports the nth day (as an integer)
on which the evaporator will be out of use.

**Note** : Content is in fact not necessary in the body of the function "evaporator", you can use it or not use it, as you wish. Some people might prefer to reason with content, some other with percentages only. It's up to you but you must keep it as a parameter because the tests have it as an argument.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ted has a pineapple. This pineapple is able to bark like a bulldog! At time t (in seconds) it barks for the first time. Then every s seconds after it, it barks twice with 1 second interval. Thus it barks at times t, t + s, t + s + 1, t + 2s, t + 2s + 1, etc.

 [Image] 

Barney woke up in the morning and wants to eat the pineapple, but he can't eat it when it's barking. Barney plans to eat it at time x (in seconds), so he asked you to tell him if it's gonna bark at that time.


-----Input-----

The first and only line of input contains three integers t, s and x (0 ≤ t, x ≤ 10^9, 2 ≤ s ≤ 10^9) — the time the pineapple barks for the first time, the pineapple barking interval, and the time Barney wants to eat the pineapple respectively.


-----Output-----

Print a single "YES" (without quotes) if the pineapple will bark at time x or a single "NO" (without quotes) otherwise in the only line of output.


-----Examples-----
Input
3 10 4

Output
NO

Input
3 10 3

Output
YES

Input
3 8 51

Output
YES

Input
3 8 52

Output
YES



-----Note-----

In the first and the second sample cases pineapple will bark at moments 3, 13, 14, ..., so it won't bark at the moment 4 and will bark at the moment 3.

In the third and fourth sample cases pineapple will bark at moments 3, 11, 12, 19, 20, 27, 28, 35, 36, 43, 44, 51, 52, 59, ..., so it will bark at both moments 51 and 52.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The latest hit song Chair Hopping contains instructions for a group dance. To perform the dance, $n$ performers numbered from $1$ to $n$ and $n$ chairs numbered from $1$ to $n$ are required. Initially, performer $i$ is seated in chair $i$.

When a single hop is performed, the performer currently seated in chair $i$ moves to chair $s_ i$. The values of $s_ i$ are distinct, ensuring that each chair will be filled by exactly one performer after the hop is completed.

Exactly two hops have been completed and now performer $i$ is sitting in chair $t_ i$. Observing that, you wonder in how many ways the values of $s_ i$ can be chosen. The answer can be large. Output it modulo $10^9 + 7$.

-----Input-----
The first line of the input contains the integer $n$ ($1 \leq n \leq 10^5$). The second line of the input contains $n$ distinct integers $t_1, t_2, \dots t_ n$ ($1 \leq t_ i \leq n$).

-----Output-----
Output the number of ways in which the values of $s_ i$ can be chosen, modulo $10^9 + 7$.

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

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kevin Sun has just finished competing in Codeforces Round #334! The round was 120 minutes long and featured five problems with maximum point values of 500, 1000, 1500, 2000, and 2500, respectively. Despite the challenging tasks, Kevin was uncowed and bulldozed through all of them, distinguishing himself from the herd as the best cowmputer scientist in all of Bovinia. Kevin knows his submission time for each problem, the number of wrong submissions that he made on each problem, and his total numbers of successful and unsuccessful hacks. Because Codeforces scoring is complicated, Kevin wants you to write a program to compute his final score.

Codeforces scores are computed as follows: If the maximum point value of a problem is x, and Kevin submitted correctly at minute m but made w wrong submissions, then his score on that problem is $\operatorname{max}(0.3 x,(1 - \frac{m}{250}) x - 50 w)$. His total score is equal to the sum of his scores for each problem. In addition, Kevin's total score gets increased by 100 points for each successful hack, but gets decreased by 50 points for each unsuccessful hack.

All arithmetic operations are performed with absolute precision and no rounding. It is guaranteed that Kevin's final score is an integer.


-----Input-----

The first line of the input contains five space-separated integers m_1, m_2, m_3, m_4, m_5, where m_{i} (0 ≤ m_{i} ≤ 119) is the time of Kevin's last submission for problem i. His last submission is always correct and gets accepted.

The second line contains five space-separated integers w_1, w_2, w_3, w_4, w_5, where w_{i} (0 ≤ w_{i} ≤ 10) is Kevin's number of wrong submissions on problem i.

The last line contains two space-separated integers h_{s} and h_{u} (0 ≤ h_{s}, h_{u} ≤ 20), denoting the Kevin's numbers of successful and unsuccessful hacks, respectively.


-----Output-----

Print a single integer, the value of Kevin's final score.


-----Examples-----
Input
20 40 60 80 100
0 1 2 3 4
1 0

Output
4900

Input
119 119 119 119 119
0 0 0 0 0
10 0

Output
4930



-----Note-----

In the second sample, Kevin takes 119 minutes on all of the problems. Therefore, he gets $(1 - \frac{119}{250}) = \frac{131}{250}$ of the points on each problem. So his score from solving problems is $\frac{131}{250}(500 + 1000 + 1500 + 2000 + 2500) = 3930$. Adding in 10·100 = 1000 points from hacks, his total score becomes 3930 + 1000 = 4930.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are going out for a walk, when you suddenly encounter N monsters. Each monster has a parameter called health, and the health of the i-th monster is h_i at the moment of encounter. A monster will vanish immediately when its health drops to 0 or below.
Fortunately, you are a skilled magician, capable of causing explosions that damage monsters. In one explosion, you can damage monsters as follows:
 - Select an alive monster, and cause an explosion centered at that monster. The health of the monster at the center of the explosion will decrease by A, and the health of each of the other monsters will decrease by B. Here, A and B are predetermined parameters, and A > B holds.
At least how many explosions do you need to cause in order to vanish all the monsters?

-----Constraints-----
 - All input values are integers.
 - 1 ≤ N ≤ 10^5
 - 1 ≤ B < A ≤ 10^9
 - 1 ≤ h_i ≤ 10^9

-----Input-----
Input is given from Standard Input in the following format:
N A B
h_1
h_2
:
h_N

-----Output-----
Print the minimum number of explosions that needs to be caused in order to vanish all the monsters.

-----Sample Input-----
4 5 3
8
7
4
2

-----Sample Output-----
2

You can vanish all the monsters in two explosion, as follows:
 - First, cause an explosion centered at the monster with 8 health. The healths of the four monsters become 3, 4, 1 and -1, respectively, and the last monster vanishes.
 - Second, cause an explosion centered at the monster with 4 health remaining. The healths of the three remaining monsters become 0, -1 and -2, respectively, and all the monsters are now vanished.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string S as input. This represents a valid date in the year 2019 in the yyyy/mm/dd format. (For example, April 30, 2019 is represented as 2019/04/30.)
Write a program that prints Heisei if the date represented by S is not later than April 30, 2019, and prints TBD otherwise.

-----Constraints-----
 - S is a string that represents a valid date in the year 2019 in the yyyy/mm/dd format.

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

-----Output-----
Print Heisei if the date represented by S is not later than April 30, 2019, and print TBD otherwise.

-----Sample Input-----
2019/04/30

-----Sample Output-----
Heisei


Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You’re playing hopscotch! You start at the origin and your goal is to hop to the lattice point $(N, N)$. A hop consists of going from lattice point $(x_1, y_1)$ to $(x_2, y_2)$, where $x_1 < x_2$ and $y_1 < y_2$.

You dislike making small hops though. You’ve decided that for every hop you make between two lattice points, the x-coordinate must increase by at least $X$ and the y-coordinate must increase by at least $Y$.

Compute the number of distinct paths you can take between $(0, 0)$ and $(N, N)$ that respect the above constraints. Two paths are distinct if there is some lattice point that you visit in one path which you don’t visit in the other.

Hint: The output involves arithmetic mod $10^9+7$. Note that with $p$ a prime like $10^9+7$, and $x$ an integer not equal to $0$ mod $p$, then $x(x^{p-2})$ mod $p$ equals $1$ mod $p$.

-----Input-----
The input consists of a line of three integers, $N$ $X$ $Y$. You may assume $1 \le X, Y \le N \le 10^{6}$.

-----Output-----
The number of distinct paths you can take between the two lattice points can be very large. Hence output this number modulo 1 000 000 007 ($10^9 + 7$).

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
INTERCAL is the oldest of esoteric programming languages. One of its many weird features is the method of character-based output, known as Turing Tape method. It converts an array of unsigned 8-bit integers into a sequence of characters to print, using the following method.

The integers of the array are processed one by one, starting from the first. Processing i-th element of the array is done in three steps:

1. The 8-bit binary notation of the ASCII-code of the previous printed character is reversed. When the first element of the array is processed, the result of this step is considered to be 0.

2. The i-th element of the array is subtracted from the result of the previous step modulo 256.

3. The binary notation of the result of the previous step is reversed again to produce ASCII-code of the i-th character to be printed.

You are given the text printed using this method. Restore the array used to produce this text.

Input

The input will consist of a single line text which contains the message printed using the described method. String text will contain between 1 and 100 characters, inclusive. ASCII-code of each character of text will be between 32 (space) and 126 (tilde), inclusive.

Output

Output the initial array, which was used to produce text, one integer per line.

Examples

Input

Hello, World!


Output

238
108
112
0
64
194
48
26
244
168
24
16
162

Note

Let's have a closer look at the beginning of the example. The first character is "H" with ASCII-code 72 = 010010002. Its reverse is 000100102 = 18, and this number should become the result of the second step of processing. The result of the first step is considered to be 0, so the first element of the array has to be (0 - 18) mod 256 = 238, where a mod b is the remainder of division of a by b.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sherlock and Watson were good friends. They both were solving a mystery. But they got hungry and wanted to eat something.
Hence they asked for some candies from Mom. Mom was also clever. She told them to solve a function for her.

Function is defined as follows - 

F(x) = 2^x - 1

She gave number "a" to Shelock and "b" to Watson and told them to solve F(a) and F(b) respectively.
After that ,she asked them how many prime numbers divide both F(a) and F(b) and they will get those numbers of candies if they answered correctly.

Your task is to calculate the number of candies that they will get from her.

Input:

First line contains an integer "t" , denoting number of testcases.
Each test case contains a single line consisting of two integers "a" and "b" separated by a single space.

Output:

Print the number of candies that Sherlock and Watson will get from Mom in a new line for each test case.

Constraints:

1 ≤ t ≤ 10^5
1 ≤ a,b ≤ 23

SAMPLE INPUT
2
1 1
2 2

SAMPLE OUTPUT
0
1

Explanation

For 1st test case , a=1, b=1.
So F(a) = 2^1 - 1 = 1
   F(b) = 2^1 - 1 = 1

No prime number divides 1. Hence answer is 0.

For 2nd test case , a=2, b=2.
So F(n,a) = 2^2 - 1 = 3
   F(n,b) = 2^2 - 1 = 3

so 3 divides 3. Hence answer is 1.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day Vasya was sitting on a not so interesting Maths lesson and making an origami from a rectangular *a* mm <=×<= *b* mm sheet of paper (*a*<=&gt;<=*b*). Usually the first step in making an origami is making a square piece of paper from the rectangular sheet by folding the sheet along the bisector of the right angle, and cutting the excess part.

After making a paper ship from the square piece, Vasya looked on the remaining (*a*<=-<=*b*) mm <=×<= *b* mm strip of paper. He got the idea to use this strip of paper in the same way to make an origami, and then use the remainder (if it exists) and so on. At the moment when he is left with a square piece of paper, he will make the last ship from it and stop.

Can you determine how many ships Vasya will make during the lesson?

Input Specification:
The first line of the input contains two integers *a*, *b* (1<=≤<=*b*<=&lt;<=*a*<=≤<=1012) — the sizes of the original sheet of paper.

Output Specification:
Print a single integer — the number of ships that Vasya will make.

Demo Input:
['2 1\n', '10 7\n', '1000000000000 1\n']

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

Note:
Pictures to the first and second sample test.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's write all the positive integer numbers one after another from $1$ without any delimiters (i.e. as a single string). It will be the infinite sequence starting with 123456789101112131415161718192021222324252627282930313233343536...

Your task is to print the $k$-th digit of this sequence.


-----Input-----

The first and only line contains integer $k$ ($1 \le k \le 10^{12}$) — the position to process ($1$-based index).


-----Output-----

Print the $k$-th digit of the resulting infinite sequence.


-----Examples-----
Input
7

Output
7

Input
21

Output
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N hidden integer arrays of length N each. You are given the mex of each of these N arrays.

Ashish likes lower bounds and Kryptonix likes upper bounds. So, for each 0 ≤ i ≤ N-1, find:
The least possible number of occurrences of i across all the arrays
The most possible number of occurrences of i across all the arrays

Note that these values must be computed independently, i.e, it is allowed to choose different configurations of arrays to attempt to minimize/maximize the number of occurrences of different integers.

Please see the samples for an example.

Recall that the mex of an array is the smallest non-negative integer that is not present in it. For example, the mex of [0, 2, 4, 1, 1, 5] is 3, and the mex of [3, 8, 101, 99, 100] is 0.

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

- The first line of input 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.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}, denoting the mexes of the N arrays.

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

For each test case, output N lines, each containing two space-separated integers. The i-th line should contain the least and the most possible number of occurrences of i across all the arrays.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 3\cdot10^{5}$
$0 ≤ A_{i} ≤ N$
- The sum of $N$ over all test cases does not exceed $3\cdot10^{5}$

----- Sample Input 1 ------ 
3
2
1 0
5
3 1 5 0 2
3
1 2 1
----- Sample Output 1 ------ 
1 2
0 2
4 13
3 13
2 13
1 13
1 15
3 8
1 2
0 4
----- explanation 1 ------ 
Test case $1$: We have the following:
- For $i = 0$, the two arrays can be $[0, 3]$ and $[2, 4]$ giving us one zero, or $[0, 0]$ and $[3, 1]$ giving us $2$ zeros.
- For $i = 1$, $[0, 4]$ and $[3, 4]$ give no ones, while $[0, 9]$ and $[1, 1]$ give $2$ ones.

Test case $3$: We have the following:
- For $i = 0$, the arrays $[0, 3, 2], [1, 0, 4], [5, 0, 2]$ give the least number of zeros (i.e, $3$), and the arrays $[0, 0, 0], [1, 0, 0], [0, 0, 0]$ give the most.
- For $i = 1$, the arrays $[5, 7, 0], [0, 3, 1], [6, 0, 3]$ give the least number of ones and the arrays $[0, 3, 2], [1, 1, 0], [5, 0, 2]$ give the most.
- For $i = 2$, the arrays $[3, 0, 9], [0, 0, 1], [0, 0, 0]$ give the least number of twos and the arrays $[2, 0, 2], [0, 1, 0], [2, 2, 0]$ give the most.

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