vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Ravi and Micro, two very good friends, had a fight today. So, Ravi challenges Micro to beat him in a game.
Ravi takes a number n to start the game.
Now, Ravi will choose integers from 0 to n sequentially (i.e.in the turn 0 he choses 0, in turn 1 he choses 1, ans so on till nth turn when he choses n).We will call this integer r for each turn.
For each turn ,the possible integers Micro can choose(in each turn, Micro can choose any number of integers) are represented by m(0 ≤ m ≤ n)

The rules of the game are:
If r+m=n, then Ravi gets r and Micro gets m(value=m , informally value is the part of n which Micro gets).
If r+m<n, then Ravi gets r and Micro gets m and remaining is not used.(value=m)
If r+m>n and:
i. If r<m, Ravi gets r , Micro gets n-r.(value=n-r)
ii.If r>m, Micro gets m, Ravi gets n-m.(value=m)
iii.If r=m,Ravi and Micro each get n/2(may be floating number).(value=n/2)

For each of the turns, Micro has to choose a set of integers(set may be singleton) such that for all the elements in the set, he gets a single value(see rules for clarification of value) which is the maximum possible value he can get when Ravi has chosen r. We call this set as M.

for given r, M={all those m for which value is maximum}.

Let the size of M in turn 0 be s0.
For r=1, size be s1 , and so on.

You have to print a number as:  s0s1s2s3......sn to help Micro, a dear friend of yours.

Example:

n=2

Now, Ravi choses integers from 0 to 2.

When Ravi chooses 0:
If Micro chooses 0, value=0
If he chooses 1, value=1
If he chooses 2, value=2

So, for r=0, M={2} as value for 2 is maximum, s0=1

When Ravi chooses 1:
If Micro chooses 0, value=0
If he chooses 1, value=1
If he chooses 2, value=1 as r=1,m=2 so r+m>n ans r

So, for r=1, M={1,2} as value=1 for both which is maximum for r=1. s1=2

When Ravi chooses 2:
If Micro chooses 0, value=0
If Micro chooses 1, r=2,m=1 , value=m=1 as r+m>n and m
If Micro chooses 2, r=2,m=2 value=1 as r+m>n and r=m so , value=n/2=2/2=1

So, for r=2, M={1,2} as value=1 for both. s2=2

So, answer for n=2 will be s0s1s2 which is 122.

Input:
The first line contains t (number of test cases).
The following t lines contain n in each line.

Output:
As specified in the question.

Constraints:
1 ≤ t ≤ 100
0 ≤ n ≤ 100000

SAMPLE INPUT
1
2

SAMPLE OUTPUT
122

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
When preparing a tournament, Codeforces coordinators try treir best to make the first problem as easy as possible. This time the coordinator had chosen some problem and asked $n$ people about their opinions. Each person answered whether this problem is easy or hard.

If at least one of these $n$ people has answered that the problem is hard, the coordinator decides to change the problem. For the given responses, check if the problem is easy enough.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 100$) — the number of people who were asked to give their opinions.

The second line contains $n$ integers, each integer is either $0$ or $1$. If $i$-th integer is $0$, then $i$-th person thinks that the problem is easy; if it is $1$, then $i$-th person thinks that the problem is hard.


-----Output-----

Print one word: "EASY" if the problem is easy according to all responses, or "HARD" if there is at least one person who thinks the problem is hard. 

You may print every letter in any register: "EASY", "easy", "EaSY" and "eAsY" all will be processed correctly.


-----Examples-----
Input
3
0 0 1

Output
HARD

Input
1
0

Output
EASY



-----Note-----

In the first example the third person says it's a hard problem, so it should be replaced.

In the second example the problem easy for the only person, so it doesn't have to be replaced.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an easier version of the next problem. In this version, $q = 0$.

A sequence of integers is called nice if its elements are arranged in blocks like in $[3, 3, 3, 4, 1, 1]$. Formally, if two elements are equal, everything in between must also be equal.

Let's define difficulty of a sequence as a minimum possible number of elements to change to get a nice sequence. However, if you change at least one element of value $x$ to value $y$, you must also change all other elements of value $x$ into $y$ as well. For example, for $[3, 3, 1, 3, 2, 1, 2]$ it isn't allowed to change first $1$ to $3$ and second $1$ to $2$. You need to leave $1$'s untouched or change them to the same value.

You are given a sequence of integers $a_1, a_2, \ldots, a_n$ and $q$ updates.

Each update is of form "$i$ $x$" — change $a_i$ to $x$. Updates are not independent (the change stays for the future).

Print the difficulty of the initial sequence and of the sequence after every update.


-----Input-----

The first line contains integers $n$ and $q$ ($1 \le n \le 200\,000$, $q = 0$), the length of the sequence and the number of the updates.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 200\,000$), the initial sequence.

Each of the following $q$ lines contains integers $i_t$ and $x_t$ ($1 \le i_t \le n$, $1 \le x_t \le 200\,000$), the position and the new value for this position.


-----Output-----

Print $q+1$ integers, the answer for the initial sequence and the answer after every update.


-----Examples-----
Input
5 0
3 7 3 7 3

Output
2

Input
10 0
1 2 1 2 3 1 1 1 50 1

Output
4

Input
6 0
6 6 3 3 4 4

Output
0

Input
7 0
3 3 1 3 2 1 2

Output
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Charles is traveling to the fantastic Fibonacci City. The city has $n$ mansions of various heights and $m$ bi-directional roads connecting the mansions. One of the most exciting tourist attraction in the city is the Fibonacci Tour, which is a simple path visiting a sequence of distinct mansions, so that every pair of consecutively visited mansions are directly connected by a road, and the heights of the mansions in the path form a continuous subsequence of the Fibonacci sequence:\[ 1, 1, 2, 3, 5, 8, \dots \]

Each number in the Fibonacci sequence equals the sum of the previous two numbers, except for the first two numbers which are defined to be one.

Charles will be happier if his tour is longer. What is the maximum length of a Fibonacci Tour he can take? The length of a tour is the number of mansions visited in the tour. Charles can start the tour at any mansion.

-----Input-----
The first line has two integers $n$ ($1\leq n\leq 10^5$) and $m$ ($0\leq m\leq 10^5$), giving the number of mansions and the number of roads in the city. The next line has $n$ positive integers no larger than $10^{18}$. The $i$-th integer gives the height of mansion $i$. The next $m$ lines each has two integers $a$ and $b$ ($1\leq a, b \leq n$, $a \neq b$), indicating that there is a bi-directional road between mansion $a$ and mansion $b$. Each pair of mansions is directly connected by at most one road.

-----Output-----
Output the length of the longest Fibonacci Tour Charles can take in the city. If there is no tour Charles can take, output zero.

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

Sample Input 2:
4 3
4 4 8 12
1 2
2 3
3 4
Sample Output 2:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an empty array A of infinite length and a positive integer K you have to process 
Q queries of type:    
- ! l r x: Fill the value x in all the empty places in the array from index l to r  (both inclusive).
- ? l r: Print the number of prime factors of K which is also a prime factor of at least one number in A[l], A[l + 1], A[l + 2], … A[r].   

-----Input-----
- The first line contains two space separated integers K and Q respectively.
- Then Q lines follow:
- Each of the $i^{th}$ line contains one of the above two types of queries.

-----Output-----
For each query of the second type, print in a new line the answer to that query. i.e. number of prime factors of K which is also a prime factor of at least one number in A[l], A[l + 1], A[l + 2], … A[r].   

-----Constraints-----
- $1 \leq K, x \leq 10^9$
- $ 1 \leq l \leq r \leq 10^5$
- $ 1 \leq Q \leq 10^5$ 

-----Sample Input-----
20 5

? 1 5

! 3 5 4

? 1 5

! 1 4 15

? 1 5   

-----Sample Output-----
0

1

2   

-----EXPLANATION-----
Initially, all the places in the array are empty. i.e _ _ _ _ _

After first update the array looks like: _ _ 4 4 4

In the range [1, 5] the only factor of 20 which is also a prime factor of at least one number in _ _ 4 4 4  is 2.

After the second update the array looks like: 15 15 4 4 4

In the range [1, 5] the prime factors of 20 i.e. 5 is a prime factor of 15, 15 and 2 is the prime factor of 4, 4, 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Count the number of strings S that satisfy the following constraints, modulo 10^9 + 7.

* The length of S is exactly N.
* S consists of digits (`0`...`9`).
* You are given Q intervals. For each i (1 \leq i \leq Q), the integer represented by S[l_i \ldots r_i] (the substring of S between the l_i-th (1-based) character and the r_i-th character, inclusive) must be a multiple of 9.



Here, the string S and its substrings may have leading zeroes. For example, `002019` represents the integer 2019.

Constraints

* 1 \leq N \leq 10^9
* 1 \leq Q \leq 15
* 1 \leq l_i \leq r_i \leq N

Input

Input is given from Standard Input in the following format:


N
Q
l_1 r_1
:
l_Q r_Q


Output

Print the number of strings that satisfy the conditions, modulo 10^9 + 7.

Examples

Input

4
2
1 2
2 4


Output

136


Input

6
3
2 5
3 5
1 3


Output

2720


Input

20
10
2 15
5 6
1 12
7 9
2 17
5 15
2 4
16 17
2 12
8 17


Output

862268030

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array arr of size N. You need to push the elements of the array into a stack and then print them while popping. 
Example 1: 
Input:
n = 5
arr = {1 2 3 4 5}
Output:
5 4 3 2 1
Example 2: 
Input: 
n = 7
arr = {1 6 43 1 2 0 5}
Output: 
5 0 2 1 43 6 1
 
Your Task:
Since this is a function problem, you don't need to take any input. Just complete the provided functions _push() and _pop().
Constraints:
1 <= A_{i} <= 10^{7}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have a string *s*<==<=*s*1*s*2...*s*|*s*|, where |*s*| is the length of string *s*, and *s**i* its *i*-th character. 

Let's introduce several definitions:
 -  A substring *s*[*i*..*j*] (1<=≤<=*i*<=≤<=*j*<=≤<=|*s*|) of string *s* is string *s**i**s**i*<=+<=1...*s**j*. -  The prefix of string *s* of length *l* (1<=≤<=*l*<=≤<=|*s*|) is string *s*[1..*l*]. -  The suffix of string *s* of length *l* (1<=≤<=*l*<=≤<=|*s*|) is string *s*[|*s*|<=-<=*l*<=+<=1..|*s*|]. 
Your task is, for any prefix of string *s* which matches a suffix of string *s*, print the number of times it occurs in string *s* as a substring.

Input Specification:
The single line contains a sequence of characters *s*1*s*2...*s*|*s*| (1<=≤<=|*s*|<=≤<=105) — string *s*. The string only consists of uppercase English letters.

Output Specification:
In the first line, print integer *k* (0<=≤<=*k*<=≤<=|*s*|) — the number of prefixes that match a suffix of string *s*. Next print *k* lines, in each line print two integers *l**i* *c**i*. Numbers *l**i* *c**i* mean that the prefix of the length *l**i* matches the suffix of length *l**i* and occurs in string *s* as a substring *c**i* times. Print pairs *l**i* *c**i* in the order of increasing *l**i*.

Demo Input:
['ABACABA\n', 'AAA\n']

Demo Output:
['3\n1 4\n3 2\n7 1\n', '3\n1 3\n2 2\n3 1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The pizza store wants to know how long each order will take. They know:

- Prepping a pizza takes 3 mins
- Cook a pizza takes 10 mins
- Every salad takes 3 mins to make
- Every appetizer takes 5 mins to make
- There are 2 pizza ovens
- 5 pizzas can fit in a oven
- Prepping for a pizza must be done before it can be put in the oven
- There are two pizza chefs and one chef for appitizers and salads combined
- The two pizza chefs can work on the same pizza

Write a function, order, which will tell the company how much time the order will take.

See example tests for details.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
Let's dive into decorators! You are given N mobile numbers. Sort them in ascending order then print them in the standard format shown below:
+91 xxxxx xxxxx

The given mobile numbers may have +91, 91 or 0 written before the actual 10 digit number. Alternatively, there may not be any prefix at all. Alternatively, there may not be any prefix at all.

=====Input Format=====
The first line of input contains an integer N, the number of mobile phone numbers. N lines follow each containing a mobile number.

=====Output Format=====
Print N mobile numbers on separate lines in the required format.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bizon the Champion isn't just friendly, he also is a rigorous coder.

Let's define function f(a), where a is a sequence of integers. Function f(a) returns the following sequence: first all divisors of a1 go in the increasing order, then all divisors of a2 go in the increasing order, and so on till the last element of sequence a. For example, f([2, 9, 1]) = [1, 2, 1, 3, 9, 1].

Let's determine the sequence Xi, for integer i (i ≥ 0): X0 = [X] ([X] is a sequence consisting of a single number X), Xi = f(Xi - 1) (i > 0). For example, at X = 6 we get X0 = [6], X1 = [1, 2, 3, 6], X2 = [1, 1, 2, 1, 3, 1, 2, 3, 6].

Given the numbers X and k, find the sequence Xk. As the answer can be rather large, find only the first 105 elements of this sequence.

Input

A single line contains two space-separated integers — X (1 ≤ X ≤ 1012) and k (0 ≤ k ≤ 1018).

Output

Print the elements of the sequence Xk in a single line, separated by a space. If the number of elements exceeds 105, then print only the first 105 elements.

Examples

Input

6 1


Output

1 2 3 6 


Input

4 2


Output

1 1 2 1 2 4 


Input

10 3


Output

1 1 1 2 1 1 5 1 1 2 1 5 1 2 5 10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef had a sequence of positive integers with length $N + K$. He managed to calculate the arithmetic average of all elements of this sequence (let's denote it by $V$), but then, his little brother deleted $K$ elements from it. All deleted elements had the same value.
Chef still knows the remaining $N$ elements — a sequence $A_1, A_2, \ldots, A_N$. Help him with restoring the original sequence by finding the value of the deleted elements or deciding that there is some mistake and the described scenario is impossible.
Note that the if it is possible for the deleted elements to have the same value, then it can be proven that it is unique. Also note that this value must be a positive integer.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains three space-separated integers $N$, $K$ and $V$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer — the value of the deleted elements, or $-1$ if there is a mistake.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N, K \le 100$
- $1 \le V \le 10^5$
- $1 \le A_i \le 10^5$ for each valid $i$

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

-----Example Input-----
3
3 3 4
2 7 3
3 1 4
7 6 5
3 3 4
2 8 3

-----Example Output-----
4
-1
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Imagine that you are in a building that has exactly n floors. You can move between the floors in a lift. Let's number the floors from bottom to top with integers from 1 to n. Now you're on the floor number a. You are very bored, so you want to take the lift. Floor number b has a secret lab, the entry is forbidden. However, you already are in the mood and decide to make k consecutive trips in the lift.

Let us suppose that at the moment you are on the floor number x (initially, you were on floor a). For another trip between floors you choose some floor with number y (y ≠ x) and the lift travels to this floor. As you cannot visit floor b with the secret lab, you decided that the distance from the current floor x to the chosen y must be strictly less than the distance from the current floor x to floor b with the secret lab. Formally, it means that the following inequation must fulfill: |x - y| < |x - b|. After the lift successfully transports you to floor y, you write down number y in your notepad.

Your task is to find the number of distinct number sequences that you could have written in the notebook as the result of k trips in the lift. As the sought number of trips can be rather large, find the remainder after dividing the number by 1000000007 (109 + 7).

Input

The first line of the input contains four space-separated integers n, a, b, k (2 ≤ n ≤ 5000, 1 ≤ k ≤ 5000, 1 ≤ a, b ≤ n, a ≠ b).

Output

Print a single integer — the remainder after dividing the sought number of sequences by 1000000007 (109 + 7).

Examples

Input

5 2 4 1


Output

2


Input

5 2 4 2


Output

2


Input

5 3 4 1


Output

0

Note

Two sequences p1, p2, ..., pk and q1, q2, ..., qk are distinct, if there is such integer j (1 ≤ j ≤ k), that pj ≠ qj.

Notes to the samples:

  1. In the first sample after the first trip you are either on floor 1, or on floor 3, because |1 - 2| < |2 - 4| and |3 - 2| < |2 - 4|. 
  2. In the second sample there are two possible sequences: (1, 2); (1, 3). You cannot choose floor 3 for the first trip because in this case no floor can be the floor for the second trip. 
  3. In the third sample there are no sought sequences, because you cannot choose the floor for the first trip.

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

Time Limit: 0 seconds

Memory Limit: 256 megabytes

Problem Description:
Tourist walks along the *X* axis. He can choose either of two directions and any speed not exceeding *V*. He can also stand without moving anywhere. He knows from newspapers that at time *t*1 in the point with coordinate *x*1 an interesting event will occur, at time *t*2 in the point with coordinate *x*2 — another one, and so on up to (*x**n*,<=*t**n*). Interesting events are short so we can assume they are immediate. Event *i* counts visited if at time *t**i* tourist was at point with coordinate *x**i*.

Write program tourist that will find maximum number of events tourist if: 
 -  at the beginning (when time is equal to 0) tourist appears at point 0, -  tourist can choose initial point for himself. 
Yes, you should answer on two similar but different questions.

Input Specification:
The first line of input contains single integer number *N* (1<=≤<=*N*<=≤<=100000) — number of interesting events. The following *N* lines contain two integers *x**i* and *t**i* — coordinate and time of the *i*-th event. The last line of the input contains integer *V* — maximum speed of the tourist. All *x**i* will be within range <=-<=2·108<=≤<=*x**i*<=≤<=2·108, all *t**i* will be between 1 and 2·106 inclusive. *V* will be positive and will not exceed 1000. The input may contain events that happen at the same time or in the same place but not in the same place at the same time.

Output Specification:
The only line of the output should contain two space-sepatated integers — maximum number of events tourist can visit in he starts moving from point 0 at time 0, and maximum number of events tourist can visit if he chooses the initial point for himself.

Demo Input:
['3\n-1 1\n42 7\n40 8\n2\n']

Demo Output:
['1 2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A wavy number is such positive integer that for any digit of its decimal representation except for the first one and the last one following condition holds: the digit is either strictly larger than both its adjacent digits or strictly less than both its adjacent digits. For example, numbers 35270, 102, 747, 20 and 3 are wavy and numbers 123, 1000 and 2212 are not.

The task is to find the k-th smallest wavy number r that is divisible by n for the given integer values n and k.

You are to write a program that will find the value of r if it doesn't exceed 1014.

Input

The only line of input contains two integers n and k, separated by a single space (1 ≤ n, k ≤ 1014). 

Output

Your task is to output the only integer r — the answer to the given problem. If such number does not exist or it is larger than 1014, then print "-1" (minus one without the quotes) instead.

Examples

Input

123 4


Output

1845


Input

100 1


Output

-1


Input

97461 457


Output

1805270103

Note

The values of the first four wavy numbers that are divisible by n for the first sample are: 492, 615, 738 and 1845.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Professor Zac is trying to finish a collection of tasks during the first week at the start of the term. He knows precisely how long each task will take, down to the millisecond. Unfortunately, it is also Frosh Week. Zac’s office window has a clear view of the stage where loud music is played. He cannot focus on any task when music is blaring.

The event organizers are also very precise. They supply Zac with intervals of time when music will not be playing. These intervals are specified by their start and end times down to the millisecond.

Each task that Zac completes must be completed in one quiet interval. He cannot pause working on a task when music plays (he loses his train of thought). Interstingly, the lengths of the tasks and quiet intervals are such that it is impossible to finish more than one task per quiet interval!

Given a list of times $t_ i$ (in milliseconds) that each task will take and a list of times $\ell _ j$ (in milliseconds) specifying the lengths of the intervals when no music is being played, what is the maximum number of tasks that Zac can complete?

-----Input-----
The first line of input contains a pair of integers $n$ and $m$, where $n$ is the number of tasks and $m$ is the number of time intervals when no music is played. The second line consists of a list of integers $t_1, t_2, \ldots , t_ n$ indicating the length of time of each task. The final line consists of a list of times $\ell _1, \ell _2, \ldots , \ell _ m$ indicating the length of time of each quiet interval when Zac is at work this week.

You may assume that $1 \leq n,m \leq 200000$ and $100000 \leq t_ i, \ell _ j \leq 199999$ for each task $i$ and each quiet interval $j$.

-----Output-----
Output consists of a single line containing a single integer indicating the number of tasks that Zac can accomplish from his list during this first week.

-----Examples-----
Sample Input 1:
5 4
150000 100000 160000 100000 180000
190000 170000 140000 160000
Sample Output 1:
4

Sample Input 2:
4 4
180000 185000 199999 100000
199999 180000 170000 120000
Sample Output 2:
3

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