vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given array a with n integers and m queries. The i-th query is given with three integers li, ri, xi.

For the i-th query find any position pi (li ≤ pi ≤ ri) so that api ≠ xi.

Input

The first line contains two integers n, m (1 ≤ n, m ≤ 2·105) — the number of elements in a and the number of queries.

The second line contains n integers ai (1 ≤ ai ≤ 106) — the elements of the array a.

Each of the next m lines contains three integers li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106) — the parameters of the i-th query.

Output

Print m lines. On the i-th line print integer pi — the position of any number not equal to xi in segment [li, ri] or the value  - 1 if there is no such number.

Examples

Input

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


Output

2
6
-1
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N men standing in a row.We can assign one of three color  R(Red),G(Green) and Black(B) to each man.
  Unfortunately,at the end we forgot that what color we assigned to each man.But we remember a list of K relationships between pairs of men.
Example 1st man and 2nd man has same color and 3rd man and 5th having different color.
  Your tast is to calculate number of possible assignmnet of colors to men.

INPUT:

Line 1:N and K. 
  Lines 2..1+K:
  Each line describes the relationship between a pair of men A and B (1 ≤ A,B ≤ N, A != B). 
  It is either of the form "1 A B", meaning that A and B have the same color, or "0 A B", meaning that A and B have different colors.

OUTPUT:

Print an Integer indicating number of possible assignmnet of colors to men.
If given information is contradictory then print 0.

Constraints:

1 ≤ N ≤ 15

1 ≤ k ≤ 50

SAMPLE INPUT
4 2 
1 1 2
0 1 3

SAMPLE OUTPUT
18

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array A = [A_{1}, A_{2}, \ldots, A_{N}], consisting of N integers. In one move, you can take two adjacent numbers A_{i} and A_{i+1}, delete them, and then insert the number A_{i} \land A_{i+1} at the deleted position. Here, \land denotes [bitwise AND]. Note that after this operation, the length of the array decreases by one.

Formally, as long as |A| > 1 (where |A| denotes the current length of A), you can pick an index 1 ≤ i < |A| and transform A into [A_{1}, A_{2}, \ldots, A_{i-1}, A_{i} \land A_{i+1}, A_{i+2}, \ldots, A_{|A|}].

Find the minimum number of moves required to make all numbers in the resulting array equal.

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

- The first line of input contains an integer T — the number of test cases you need to solve.
- 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}, \ldots, A_{N} — the elements of the array A.

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

For each test case, output on a new line the minimum number of moves required to make all numbers equal.

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

$1 ≤T ≤10^{6}$
$2 ≤N ≤10^{6}$
- Sum of $N$ over all test cases is at most $10^{6}$.
$0 ≤A_{i} < 2^{30}$

------ subtasks ------ 

Subtask 1 (20 points):
$0 ≤A_{i} ≤255$
Sum of $N$ over all test cases is at most $255$.
Subtask 2 (30 points):
Sum of $N$ over all test cases is at most $2000$.
Subtask 3 (50 points):
Original constraints.

----- Sample Input 1 ------ 
4
4
0 0 0 1
2
1 1
6
1 2 3 4 5 6
4
2 28 3 22

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

----- explanation 1 ------ 
Test case $1$: Choose $i = 3$ to make the array $[0, 0, 0 \land 1] = [0, 0, 0]$.

Test case $2$: All elements of the array are already equal.

Test case $3$: One possible sequence of moves is as follows:
- Choose $i = 1$, making the array $[1\land 2, 3, 4, 5, 6] = [0, 3, 4, 5, 6]$
- Choose $i = 2$, making the array $[0, 0, 5, 6]$
- Choose $i = 3$, making the array $[0, 0, 4]$
- Choose $i = 2$, making the array $[0, 0]$

It can be verified that in this case, making every element equal using $3$ or fewer moves is impossible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Henry and Derek are waiting on a room, eager to join the Snackdown 2016 Qualifier Round. They decide to pass the time by playing a game.  
In this game's setup, they write N positive integers on a blackboard. Then the players take turns, starting with Henry. In a turn, a player selects one of the integers, divides it by 2, 3, 4, 5 or 6, and then takes the floor to make it an integer again. If the integer becomes 0, it is erased from the board. The player who makes the last move wins.  

Henry and Derek are very competitive, so aside from wanting to win Snackdown, they also want to win this game. Assuming they play with the optimal strategy, your task is to predict who wins the game.  

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of integers they wrote on the board. The second line contains N space-separated integers A1, A2, ..., AN denoting the integers themselves.

-----Output-----
For each test case, output a single line containing either “Henry” or “Derek” (without quotes), denoting the winner of the game.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 100
- 1 ≤ Ai ≤ 1018

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

Output:Henry
Derek

-----Explanation-----
Example case 1. In this test case, the numbers on the board are [3,4]. Henry can win by selecting 4 and then dividing it by 2. The integers on the board are now [3,2]. Derek now has a couple of choices:
- Derek can divide 2 by 3, 4, 5 or 6, making it 0 and removing it. Now only one integer remains on the board, 3, and Henry can just divide it by 6 to finish, and win, the game.
- Derek can divide 3 by 4, 5 or 6, making it 0 and removing it. Now only one integer remains on the board, 2, and Henry can just divide it by 6 to finish, and win, the game.
- Derek can divide 2 by 2. Now the integers are [1,3]. Henry can respond by dividing 3 by 3. The integers are now [1,1]. Now Derek has no choice but to divide 1 by 2, 3, 4, 5 or 6 and remove it (because it becomes 0). Henry can respond by dividing the remaining 1 by 2 to finish, and win, the game.
- Derek can divide 3 by 2 or 3. Now the integers are [1,2]. Henry can respond by dividing 2 by 2. The integers are now [1,1]. This leads to a situation as in the previous case and Henry wins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little penguin Polo likes permutations. But most of all he likes permutations of integers from 0 to n, inclusive.

For permutation p = p_0, p_1, ..., p_{n}, Polo has defined its beauty — number $(0 \oplus p_{0}) +(1 \oplus p_{1}) + \cdots +(n \oplus p_{n})$.

Expression $x \oplus y$ means applying the operation of bitwise excluding "OR" to numbers x and y. This operation exists in all modern programming languages, for example, in language C++ and Java it is represented as "^" and in Pascal — as "xor".

Help him find among all permutations of integers from 0 to n the permutation with the maximum beauty.


-----Input-----

The single line contains a positive integer n (1 ≤ n ≤ 10^6).


-----Output-----

In the first line print integer m the maximum possible beauty. In the second line print any permutation of integers from 0 to n with the beauty equal to m.

If there are several suitable permutations, you are allowed to print any of them.


-----Examples-----
Input
4

Output
20
0 2 1 4 3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You're trying to set the record on your favorite video game. The game consists of *N* levels, which must be completed sequentially in order to beat the game. You usually complete each level as fast as possible, but sometimes finish a level slower. Specifically, you will complete the *i*-th level in either *F**i* seconds or *S**i* seconds, where *F**i*<=&lt;<=*S**i*, and there's a *P**i* percent chance of completing it in *F**i* seconds. After completing a level, you may decide to either continue the game and play the next level, or reset the game and start again from the first level. Both the decision and the action are instant.

Your goal is to complete all the levels sequentially in at most *R* total seconds. You want to minimize the expected amount of time playing before achieving that goal. If you continue and reset optimally, how much total time can you expect to spend playing?

Input Specification:
The first line of input contains integers *N* and *R* , the number of levels and number of seconds you want to complete the game in, respectively. *N* lines follow. The *i*th such line contains integers *F**i*,<=*S**i*,<=*P**i* (1<=≤<=*F**i*<=&lt;<=*S**i*<=≤<=100,<=80<=≤<=*P**i*<=≤<=99), the fast time for level *i*, the slow time for level *i*, and the probability (as a percentage) of completing level *i* with the fast time.

Output Specification:
Print the total expected time. Your answer must be correct within an absolute or relative error of 10<=-<=9.

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

Demo Input:
['1 8\n2 8 81\n', '2 30\n20 30 80\n3 9 85\n', '4 319\n63 79 89\n79 97 91\n75 87 88\n75 90 83\n']

Demo Output:
['3.14\n', '31.4\n', '314.159265358\n']

Note:
In the first example, you never need to reset. There's an 81% chance of completing the level in 2 seconds and a 19% chance of needing 8 seconds, both of which are within the goal time. The expected time is 0.81·2 + 0.19·8 = 3.14.

In the second example, you should reset after the first level if you complete it slowly. On average it will take 0.25 slow attempts before your first fast attempt. Then it doesn't matter whether you complete the second level fast or slow. The expected time is 0.25·30 + 20 + 0.85·3 + 0.15·9 = 31.4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The new camp by widely-known over the country Spring Programming Camp is going to start soon. Hence, all the team of friendly curators and teachers started composing the camp's schedule. After some continuous discussion, they came up with a schedule s, which can be represented as a binary string, in which the i-th symbol is '1' if students will write the contest in the i-th day and '0' if they will have a day off.

At the last moment Gleb said that the camp will be the most productive if it runs with the schedule t (which can be described in the same format as schedule s). Since the number of days in the current may be different from number of days in schedule t, Gleb required that the camp's schedule must be altered so that the number of occurrences of t in it as a substring is maximum possible. At the same time, the number of contest days and days off shouldn't change, only their order may change.

Could you rearrange the schedule in the best possible way?

Input

The first line contains string s (1 ⩽ |s| ⩽ 500 000), denoting the current project of the camp's schedule.

The second line contains string t (1 ⩽ |t| ⩽ 500 000), denoting the optimal schedule according to Gleb.

Strings s and t contain characters '0' and '1' only.

Output

In the only line print the schedule having the largest number of substrings equal to t. Printed schedule should consist of characters '0' and '1' only and the number of zeros should be equal to the number of zeros in s and the number of ones should be equal to the number of ones in s.

In case there multiple optimal schedules, print any of them.

Examples

Input


101101
110


Output


110110

Input


10010110
100011


Output


01100011


Input


10
11100


Output


01

Note

In the first example there are two occurrences, one starting from first position and one starting from fourth position.

In the second example there is only one occurrence, which starts from third position. Note, that the answer is not unique. For example, if we move the first day (which is a day off) to the last position, the number of occurrences of t wouldn't change.

In the third example it's impossible to make even a single occurrence.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 You are given a string consisting of `"D", "P" and "C"`. A positive integer N is called DPC of this string if it satisfies the following properties: 
 
 ```
 For each i = 1, 2, ... , size of the string:

 If i-th character is "D", then N can be divided by i
 If i-th character is "P", then N and i should be relatively prime
 If i-th character is "C", then N should neither be divided by i 
                           nor be relatively prime with i```

Your task is to find the smallest DPC of a given string, or return `-1` if there is no such. The result is guaranteed to be `<= 10^9`.

# Example
 For `s = "DDPDD"`, the result should be `20`.
 
 `"DDPDD"` means `N` should `divided by 1,2,4,5`, and `N,3` should be relatively prime. The smallest N should be `20`.

# Input/Output


 - `[input]` string `s`

  The given string


 - `[output]` an integer

  The smallest DPC of `s` or `-1` if it doesn't exist.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mashmokh's boss, Bimokh, didn't like Mashmokh. So he fired him. Mashmokh decided to go to university and participate in ACM instead of finding a new job. He wants to become a member of Bamokh's team. In order to join he was given some programming tasks and one week to solve them. Mashmokh is not a very experienced programmer. Actually he is not a programmer at all. So he wasn't able to solve them. That's why he asked you to help him with these tasks. One of these tasks is the following.

A sequence of l integers b1, b2, ..., bl (1 ≤ b1 ≤ b2 ≤ ... ≤ bl ≤ n) is called good if each number divides (without a remainder) by the next number in the sequence. More formally <image> for all i (1 ≤ i ≤ l - 1).

Given n and k find the number of good sequences of length k. As the answer can be rather large print it modulo 1000000007 (109 + 7).

Input

The first line of input contains two space-separated integers n, k (1 ≤ n, k ≤ 2000).

Output

Output a single integer — the number of good sequences of length k modulo 1000000007 (109 + 7).

Examples

Input

3 2


Output

5


Input

6 4


Output

39


Input

2 1


Output

2

Note

In the first sample the good sequences are: [1, 1], [2, 2], [3, 3], [1, 2], [1, 3].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A Pythagorean triple is a triple of integer numbers (a, b, c) such that it is possible to form a right triangle with the lengths of the first cathetus, the second cathetus and the hypotenuse equal to a, b and c, respectively. An example of the Pythagorean triple is (3, 4, 5).

Vasya studies the properties of right triangles, and he uses a formula that determines if some triple of integers is Pythagorean. Unfortunately, he has forgotten the exact formula; he remembers only that the formula was some equation with squares. So, he came up with the following formula: c = a^2 - b.

Obviously, this is not the right formula to check if a triple of numbers is Pythagorean. But, to Vasya's surprise, it actually worked on the triple (3, 4, 5): 5 = 3^2 - 4, so, according to Vasya's formula, it is a Pythagorean triple.

When Vasya found the right formula (and understood that his formula is wrong), he wondered: how many are there triples of integers (a, b, c) with 1 ≤ a ≤ b ≤ c ≤ n such that they are Pythagorean both according to his formula and the real definition? He asked you to count these triples.

Input

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

Each test case consists of one line containing one integer n (1 ≤ n ≤ 10^9).

Output

For each test case, print one integer — the number of triples of integers (a, b, c) with 1 ≤ a ≤ b ≤ c ≤ n such that they are Pythagorean according both to the real definition and to the formula Vasya came up with.

Example

Input


3
3
6
9


Output


0
1
1

Note

The only Pythagorean triple satisfying c = a^2 - b with 1 ≤ a ≤ b ≤ c ≤ 9 is (3, 4, 5); that's why the answer for n = 3 is 0, and the answer for n = 6 (and for n = 9) is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nature photographing may be fun for tourists, but it is one of the most complicated things for photographers. To capture all the facets of a bird, you might need more than one cameras. You recently encountered such a situation.
There are $n$ photographers, so there are $n$ cameras in a line on the x-axis. All the cameras are at distinct coordinates. 
You want to pair up these cameras ($n$ is even) in such a way that the sum of angles subtended on the bird by the pair of cameras is maximized. Formally, let A, B be two cameras, and let P be the bird to be captured by these two cameras. The angle will APB. 
Note: All angles are in radians.

-----Input-----
- The first line of the input contains an integer $T$ denoting the number of test cases. The description of the test cases follows.
- The first line of each test case contains an integer $n$.
- The second line of each test case contains $n$ space-separated integers denoting the $x_i$ coordinates of the cameras.
- The third line of each test case contains two space-separated integers $P, Q$ denoting the x and y coordinates of the bird respectively.

-----Output-----
For each test case, output your answer in a single line. Your answer would be considered correct if its absolute error is less than or equal to 1e-6 of the actual answer. 

-----Constraints-----
- $1 \le T \le 10$
- $2 \le n \leq  100$
- $1 \le x_i \leq 300$
- $0 \le P \leq 300$
- $1 \le Q \leq 300$

-----Example Input-----
2
2
0 1
0 1
2
0 1
100 1

-----Example Output-----
0.785398163397
0.000100999899

-----Explanation-----
Note: $1 \leq x_i$ is not being satisfied by the sample input, but will be satisfied in the actual test data.
Testcase 1: There are only 2 cameras, so they have to paired up with each other. And the angle subtended by then is 45 degrees. Converting this to radians gives the output.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In an array A of 0s and 1s, how many non-empty subarrays have sum S?
 
Example 1:
Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation: 
The 4 subarrays are bolded below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]

 
Note:

A.length <= 30000
0 <= S <= A.length
A[i] is either 0 or 1.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let's define a string &lt;x&gt; as an opening tag, where *x* is any small letter of the Latin alphabet. Each opening tag matches a closing tag of the type &lt;/x&gt;, where *x* is the same letter.

Tegs can be nested into each other: in this case one opening and closing tag pair is located inside another pair.

Let's define the notion of a XML-text: 
 -  an empty string is a XML-text -  if *s* is a XML-text, then *s*'=&lt;a&gt;+*s*+&lt;/a&gt; also is a XML-text, where *a* is any small Latin letter -  if *s*1, *s*2 are XML-texts, then *s*1+*s*2 also is a XML-text 
You are given a XML-text (it is guaranteed that the text is valid), your task is to print in the following form: 
 -  each tag (opening and closing) is located on a single line -  print before the tag 2<=*<=*h* spaces, where *h* is the level of the tag's nestedness.

Input Specification:
The input data consists on the only non-empty string — the XML-text, its length does not exceed 1000 characters. It is guaranteed that the text is valid. The text contains no spaces.

Output Specification:
Print the given XML-text according to the above-given rules.

Demo Input:
['&lt;a&gt;&lt;b&gt;&lt;c&gt;&lt;/c&gt;&lt;/b&gt;&lt;/a&gt;\n', '&lt;a&gt;&lt;b&gt;&lt;/b&gt;&lt;d&gt;&lt;c&gt;&lt;/c&gt;&lt;/d&gt;&lt;/a&gt;\n']

Demo Output:
['&lt;a&gt;\n  &lt;b&gt;\n    &lt;c&gt;\n    &lt;/c&gt;\n  &lt;/b&gt;\n&lt;/a&gt;\n', '&lt;a&gt;\n  &lt;b&gt;\n  &lt;/b&gt;\n  &lt;d&gt;\n    &lt;c&gt;\n    &lt;/c&gt;\n  &lt;/d&gt;\n&lt;/a&gt;\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Misha was interested in water delivery from childhood. That's why his mother sent him to the annual Innovative Olympiad in Irrigation (IOI). Pupils from all Berland compete there demonstrating their skills in watering. It is extremely expensive to host such an olympiad, so after the first $n$ olympiads the organizers introduced the following rule of the host city selection.

The host cities of the olympiads are selected in the following way. There are $m$ cities in Berland wishing to host the olympiad, they are numbered from $1$ to $m$. The host city of each next olympiad is determined as the city that hosted the olympiad the smallest number of times before. If there are several such cities, the city with the smallest index is selected among them.

Misha's mother is interested where the olympiad will be held in some specific years. The only information she knows is the above selection rule and the host cities of the first $n$ olympiads. Help her and if you succeed, she will ask Misha to avoid flooding your house.


-----Input-----

The first line contains three integers $n$, $m$ and $q$ ($1 \leq n, m, q \leq 500\,000$) — the number of olympiads before the rule was introduced, the number of cities in Berland wishing to host the olympiad, and the number of years Misha's mother is interested in, respectively.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq m$), where $a_i$ denotes the city which hosted the olympiad in the $i$-th year. Note that before the rule was introduced the host city was chosen arbitrarily.

Each of the next $q$ lines contains an integer $k_i$ ($n + 1 \leq k_i \leq 10^{18}$) — the year number Misha's mother is interested in host city in.


-----Output-----

Print $q$ integers. The $i$-th of them should be the city the olympiad will be hosted in the year $k_i$.


-----Examples-----
Input
6 4 10
3 1 1 1 2 2
7
8
9
10
11
12
13
14
15
16

Output
4
3
4
2
3
4
1
2
3
4

Input
4 5 4
4 4 5 1
15
9
13
6

Output
5
3
3
3



-----Note-----

In the first example Misha's mother is interested in the first $10$ years after the rule was introduced. The host cities these years are 4, 3, 4, 2, 3, 4, 1, 2, 3, 4.

In the second example the host cities after the new city is introduced are 2, 3, 1, 2, 3, 5, 1, 2, 3, 4, 5, 1.

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