vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
C: Shuttle Run

Story

University H has a unique physical fitness test program, aiming to grow the mindset of students. Among the items in the program, shuttle run is well-known as especially eccentric one. Surprisingly, there are yokans (sweet beans jellies) on a route of the shuttle run. Greedy Homura-chan would like to challenge to eat all the yokans. And lazy Homura-chan wants to make the distance she would run as short as possible. For her, you decided to write a program to compute the minimum distance she would run required to eat all the yokans.

Problem Statement

At the beginning of a shuttle run, Homura-chan is at 0  in a positive direction on a number line. During the shuttle run, Homura-chan repeats the following moves:

* Move in a positive direction until reaching M.
* When reaching M, change the direction to negative.
* Move in a negative direction until reaching 0 .
* When reaching 0 , change the direction to positive.



During the moves, Homura-chan also eats yokans on the number line. There are N yokans on the number line. Initially, the i-th yokan, whose length is R_i - L_i, is at an interval [L_i, R_i] on the number line. When Homura-chan reaches L_i in a positive direction (or R_i in a negative direction), she can start eating the i-th yokan from L_i to R_i (or from R_i to L_i), and then the i-th yokan disappears. Unfortunately, Homura-chan has only one mouth. So she cannot eat two yokans at the same moment, including even when she starts eating and finishes eating (See the example below). Also, note that she cannot stop eating in the middle of yokan and has to continue eating until she reaches the other end of the yokan she starts eating; it's her belief.

Calculate the minimum distance Homura-chan runs to finish eating all the yokans. The shuttle run never ends until Homura-chan eats all the yokans.

Input


N M
L_1 R_1
:
L_N R_N


The first line contains two integers N and M. The following N lines represent the information of yokan, where the i-th of them contains two integers L_i and R_i corresponding to the interval [L_i, R_i] the i-th yokan is.

Constraints

* 1 \leq N \leq 2 \times 10^5
* 3 \leq M \leq 10^9
* 0 < L_i < R_i < M
* Inputs consist only of integers.



Output

Output the minimum distance Homura-chan runs to eat all the given yokan in a line.

Sample Input 1


1 3
1 2


Output for Sample Input 1


2

Sample Input 2


2 5
1 2
2 4


Output for Sample Input 2


8

Note that when Homura-chan is at the coordinate 2, she cannot eat the first and second yokan at the same time.





Example

Input

1 3
1 2


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Iahub and Iahubina went to a date at a luxury restaurant. Everything went fine until paying for the food. Instead of money, the waiter wants Iahub to write a Hungry sequence consisting of n integers. 

A sequence a1, a2, ..., an, consisting of n integers, is Hungry if and only if: 

  * Its elements are in increasing order. That is an inequality ai < aj holds for any two indices i, j (i < j). 
  * For any two indices i and j (i < j), aj must not be divisible by ai. 



Iahub is in trouble, so he asks you for help. Find a Hungry sequence with n elements.

Input

The input contains a single integer: n (1 ≤ n ≤ 105).

Output

Output a line that contains n space-separated integers a1 a2, ..., an (1 ≤ ai ≤ 107), representing a possible Hungry sequence. Note, that each ai must not be greater than 10000000 (107) and less than 1.

If there are multiple solutions you can output any one.

Examples

Input

3


Output

2 9 15


Input

5


Output

11 14 20 27 31

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set $\mbox{A}$ and $n$ other sets. 

Your job is to find whether set $\mbox{A}$ is a strict superset of each of the $N$ sets.   

Print True, if $\mbox{A}$ is a strict superset of each of the $N$ sets. Otherwise, print False. 

A strict superset has at least one element that does not exist in its subset.  

Example 

Set$([1,3,4])$ is a strict superset of set$([1,3])$. 

Set$([1,3,4])$ is not a strict superset of set$([1,3,4])$. 

Set$([1,3,4])$ is not a strict superset of set$([1,3,5])$.  

Input Format

The first line contains the space separated elements of set $\mbox{A}$. 

The second line contains integer $n$, the number of other sets. 

The next $n$ lines contains the space separated elements of the other sets.  

Constraints

$0<len(set(A))<501$   
$0\lt N\lt21$  
$0<len(otherSets)<101$  

Output Format

Print True if set $\mbox{A}$ is a strict superset of all other $N$ sets. Otherwise, print False.

Sample Input 0
1 2 3 4 5 6 7 8 9 10 11 12 23 45 84 78
2
1 2 3 4 5
100 11 12

Sample Output 0
False

Explanation 0

Set $\mbox{A}$ is the strict superset of the set$([1,2,3,4,5])$ but not of the set$([100,11,12])$ because $\left(\begin{array}{c c}{{1}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ {{0}}&{{0}}&{{0}}&{{0}}\\ \end{array}\right).$ is not in set $\mbox{A}$. 

Hence, the output is False.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You've just entered a programming contest and have a chance to win a million dollars. This is the last question you have to solve, so your victory (and your vacation) depend on it. Can you guess the function just by looking at the test cases? There are two numerical inputs and one numerical output. Goodluck!

hint: go
 here

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Alice likes snow a lot! Unfortunately, this year's winter is already over, and she can't expect to have any more of it. Bob has thus bought her a gift — a large snow maker. He plans to make some amount of snow every day. On day *i* he will make a pile of snow of volume *V**i* and put it in her garden.

Each day, every pile will shrink a little due to melting. More precisely, when the temperature on a given day is *T**i*, each pile will reduce its volume by *T**i*. If this would reduce the volume of a pile to or below zero, it disappears forever. All snow piles are independent of each other. 

Note that the pile made on day *i* already loses part of its volume on the same day. In an extreme case, this may mean that there are no piles left at the end of a particular day.

You are given the initial pile sizes and the temperature on each day. Determine the total volume of snow melted on each day.

Input Specification:
The first line contains a single integer *N* (1<=≤<=*N*<=≤<=105) — the number of days. 

The second line contains *N* integers *V*1,<=*V*2,<=...,<=*V**N* (0<=≤<=*V**i*<=≤<=109), where *V**i* is the initial size of a snow pile made on the day *i*.

The third line contains *N* integers *T*1,<=*T*2,<=...,<=*T**N* (0<=≤<=*T**i*<=≤<=109), where *T**i* is the temperature on the day *i*.

Output Specification:
Output a single line with *N* integers, where the *i*-th integer represents the total volume of snow melted on day *i*.

Demo Input:
['3\n10 10 5\n5 7 2\n', '5\n30 25 20 15 10\n9 10 12 4 13\n']

Demo Output:
['5 12 4\n', '9 20 35 11 25\n']

Note:
In the first sample, Bob first makes a snow pile of volume 10, which melts to the size of 5 on the same day. On the second day, he makes another pile of size 10. Since it is a bit warmer than the day before, the first pile disappears completely while the second pile shrinks to 3. At the end of the second day, he has only a single pile of size 3. On the third day he makes a smaller pile than usual, but as the temperature dropped too, both piles survive till the end of the day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider an array that has no prime numbers, and none of its elements has any prime digit. It would start with: `[1,4,6,8,9,10,14,16,18,..]`. 

`12` and `15` are not in the list because `2` and `5` are primes.

You will be given an integer `n` and your task will be return the number at that index in the array. 
For example:
```
solve(0) = 1
solve(2) = 6
``` 

More examples in the test cases.

Good luck!

If you like Prime Katas, you will enjoy this Kata: [Simple Prime Streaming](https://www.codewars.com/kata/5a908da30025e995880000e3)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.


Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.



Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your job is to return the volume of a cup when given the diameter of the top, the diameter of the bottom and the height.

You know that there is a steady gradient from the top to the bottom.

You want to return the volume rounded to 2 decimal places.

Exmples:
```python
cup_volume(1, 1, 1)==0.79

cup_volume(10, 8, 10)==638.79

cup_volume(1000, 1000, 1000)==785398163.4

cup_volume(13.123, 123.12, 1)==4436.57

cup_volume(5, 12, 31)==1858.51
```

You will only be passed positive numbers.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.
We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

-----Constraints-----
 - 1 ≤ K ≤ N ≤ 200000
 - 1 ≤ p_i ≤ 1000
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
p_1 ... p_N

-----Output-----
Print the maximum possible value of the expected value of the sum of the numbers shown.
Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-6}.

-----Sample Input-----
5 3
1 2 2 4 5

-----Sample Output-----
7.000000000000

When we throw the third, fourth, and fifth dice from the left, the expected value of the sum of the numbers shown is 7. This is the maximum value we can achieve.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Xenny and his friends came to know about a mobile phone product called NplusN, which could be bought if a person sent invitations to others to buy the phone.

They started sending and receiving several invitations of the highly coveted product.

There was however, a twist in the tale. The Association of CodeSprinters (ACS) announced that Xenny was the senior-most inviter among his friends, so the hierarchy would start from him. Every person was then assigned a hierarchy level (H), depending on how many intermediate people it took for an invitation to reach a person.

For example,

Consider the hierarchy:

Xenny -> Penny -> Sunny

in this case, the hierarchy level of Xenny is highest, hierarchy level of Penny is lower than Xenny but higher than Sunny, and hierarchy level of Sunny is the lowest among them all.

The ACS made some more rules:

For a certain person, only those invites will be considered which he made to people who were lower in the hierarchy as compared to him/her.

The total of a person's invites would be equal to the sum of invites sent by everyone who is just below him/her in the hierarchy.

People in the lowest level of hierarchy have 1 invite.

For example, in the above case, Sunny's number of invites would be 1, Jenny's invites would be 1 and Xenny's invites would be 1 as well.

Xenny's friend, Bhavesh, already had an awesome phone and wasn't interested in sending/receiving NplusN invites. So, he decided to perform some analytics on the entire scenario of invitations.

He had a list of every member's unique ID and a list of all exchanges of invitations, i.e., if a person A exchanged an invitation with person B, either A sent the invitation to B, or B sent the invitation to A - both cases were possible.

Help Bhavesh in finding out the total number of invites sent by each person.

Input Format

First lines contains 2 space-separated positive integers - N and M - denoting the number of people and the number of exchanges respectively.

M lines follow. Each line contains 2 space-separated integers X and Y - denoting an exchange of invitation between people with unique IDs X and Y.

Last line of input contains a single integer S - denoting the unique ID of Xenny.

Output Format

Output N space-separated integers, each denoting the number of invites of the i^th person.

Constraints

1 ≤ N ≤ 10^5

1 ≤ M ≤ 5 * 10^5

1 ≤ X, Y, S ≤ N

SAMPLE INPUT
6 7
1 2
1 3
1 5
3 4
4 5
4 6
5 6
1

SAMPLE OUTPUT
3 0 1 1 2 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shridhar wants to generate some prime numbers for his cryptosystem. Help him!
Your task is to generate all prime numbers between two given numbers.


Input

The first line contains t, the number of test cases (less then or equal to 10). 

Followed by t lines which contain two numbers m and n (1 ≤ m ≤ n ≤ 1000000000, n-m ≤ 100000) separated by a space.


Output
For every test case print all prime numbers p such that m ≤ p ≤ n,
one number per line.  Separate the answers for each test case by an empty line.

Example
Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
How many n-digit numbers (without leading zeros) are there such that no digit occurs more than k times?  

As the count of such n-digit numbers can be very large, print the answer mod (10^{9}+7)  

Input Format  

The first line contains an integer, T , the number of test cases. This is followed by T lines each containing 2 space separated integers, n and k  

Constraints  

T ≤ 100000 

1 ≤ n ≤ 1000 

1 ≤ k ≤ 10^{9}

Sample Input

2
2 3
2 1

Sample Output

90
81

Explanation 

Case 1: A number can appear three times. So we have 9 (all except 0) numbers for first digit and 10 numbers for the second digit. 

Case 2: A number can appear only once. So we have 9 choices for the first digit and 9(all except the first one) for the second digit.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is an infinite set generated as follows:

  * 1 is in this set. 
  * If x is in this set, x ⋅ a and x+b both are in this set. 



For example, when a=3 and b=6, the five smallest elements of the set are:

  * 1, 
  * 3 (1 is in this set, so 1⋅ a=3 is in this set), 
  * 7 (1 is in this set, so 1+b=7 is in this set), 
  * 9 (3 is in this set, so 3⋅ a=9 is in this set), 
  * 13 (7 is in this set, so 7+b=13 is in this set). 



Given positive integers a, b, n, determine if n is in this set.

Input

The input consists of multiple test cases. The first line contains an integer t (1≤ t≤ 10^5) — the number of test cases. The description of the test cases follows.

The only line describing each test case contains three integers n, a, b (1≤ n,a,b≤ 10^9) separated by a single space.

Output

For each test case, print "Yes" if n is in this set, and "No" otherwise. You can print each letter in any case.

Example

Input


5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264


Output


Yes
No
Yes
No
Yes

Note

In the first test case, 24 is generated as follows:

  * 1 is in this set, so 3 and 6 are in this set; 
  * 3 is in this set, so 9 and 8 are in this set; 
  * 8 is in this set, so 24 and 13 are in this set. 



Thus we can see 24 is in this set.

The five smallest elements of the set in the second test case is described in statements. We can see that 10 isn't among them.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two arrays $a$ and $b$, each contains $n$ integers.

You want to create a new array $c$ as follows: choose some real (i.e. not necessarily integer) number $d$, and then for every $i \in [1, n]$ let $c_i := d \cdot a_i + b_i$.

Your goal is to maximize the number of zeroes in array $c$. What is the largest possible answer, if you choose $d$ optimally?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in both arrays.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($-10^9 \le a_i \le 10^9$).

The third line contains $n$ integers $b_1$, $b_2$, ..., $b_n$ ($-10^9 \le b_i \le 10^9$).


-----Output-----

Print one integer — the maximum number of zeroes in array $c$, if you choose $d$ optimally.


-----Examples-----
Input
5
1 2 3 4 5
2 4 7 11 3

Output
2

Input
3
13 37 39
1 2 3

Output
2

Input
4
0 0 0 0
1 2 3 4

Output
0

Input
3
1 2 -1
-6 -12 6

Output
3



-----Note-----

In the first example, we may choose $d = -2$.

In the second example, we may choose $d = -\frac{1}{13}$.

In the third example, we cannot obtain any zero in array $c$, no matter which $d$ we choose.

In the fourth example, we may choose $d = 6$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A sequence of integers ($a_1, a_2, \ldots, a_k$) is said to be UpDown, if these inequalities hold true:
- $a_1 \le a_2$
- $a_2 \ge a_3$
- $a_3 \le a_4$
and so on.
That is, every even-indexed element should be at least as large as its adjacent elements. And every odd-indexed element should be at most as large as its adjacent elements. Formally, $a_{2i} \ge a_{2i+1}$ and $a_{2i+1} \le a_{2i+2}$, for all valid positions.
A subsegment is a consecutive portion of a sequence. That is, a subsegment of ($b_1, b_2, \ldots, b_k$)  will be of the form ($b_i, b_{i+1}, \ldots, b_j$), for some $i$ and $j$.
You are given a sequence ($s_1, s_2, \ldots, s_n$). You can insert at most one integer anywhere in this sequence. It could be any integer. After inserting an integer (or choosing not to), suppose you have the new sequence ($t_1, t_2, \ldots, t_m$). Note that $m$ will either be $n$+1 or $n$. You want to maximize the length of the longest subsegment of ($t_1, t_2, \ldots, t_m$) which is UpDown, and output the length of that.

-----Input-----
- The first line contains a single integer, $T$, which is the number of testcases. The description of each testcase follows.
- The first line of every testcase contains a single integer, $n$, which is the number of integers in the original sequence.
- The second line contains $n$ integers: $s_1, s_2, \ldots, s_n$, which forms the original sequence.

-----Output-----
For each testcase output a single line containing one integer, which should be the length of the longest UpDown subsegment that you can get after inserting at most one integer.

-----Constraints-----
- $1 \le T \le 2$
- $1 \le n \le 10^6$
- $1 \le s_i \le 10^9$

-----Subtasks-----
Subtask #1 (20 points): $1 \le n \le 100$
Subtask #2 (10 points): $1 \le n \le 10000$
Subtask #3 (70 points): Original constraints

-----Sample Input-----
2
7
100 1 10 3 20 25 24
5
3 3 2 4 1

-----Sample Output-----
7
6

-----Explanation-----
Testcase 1: The original sequence is (100, 1, 10, 3, 20, 25, 24). Suppose you insert the element 5 between the elements 20 and 25, you will get the new sequence (100, 1, 10, 3, 20, 5, 25, 24). The longest UpDown subsegment of this sequence is (1, 10, 3, 20, 5, 25, 24), whose length is 7. You can check that you cannot do any better, and hence the answer is 7.
Testcase 2: The original sequence is (3, 3, 2, 4, 1). Suppose you insert the element 4 at the end, you will get the new sequence (3, 3, 2, 4, 1, 4). This entire sequence is UpDown, and so the longest UpDown subsegment of this sequence is (3, 3, 2, 4, 1, 4), whose length is 6. You can check that you cannot do any better, and hence the answer is 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
(This problem is the same as Minimize Malware Spread, with the differences bolded.)
In a network of nodes, each node i is directly connected to another node j if and only if graph[i][j] = 1.
Some nodes initial are initially infected by malware.  Whenever two nodes are directly connected and at least one of those two nodes is infected by malware, both nodes will be infected by malware.  This spread of malware will continue until no more nodes can be infected in this manner.
Suppose M(initial) is the final number of nodes infected with malware in the entire network, after the spread of malware stops.
We will remove one node from the initial list, completely removing it and any connections from this node to any other node.  Return the node that if removed, would minimize M(initial).  If multiple nodes could be removed to minimize M(initial), return such a node with the smallest index.
 



Example 1:
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0


Example 2:
Input: graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
Output: 1


Example 3:
Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
Output: 1

 
Note:

1 < graph.length = graph[0].length <= 300
0 <= graph[i][j] == graph[j][i] <= 1
graph[i][i] = 1
1 <= initial.length < graph.length
0 <= initial[i] < graph.length

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your fancy debugger will not help you in this matter. There are many ways in which code can produce different behavior between debug and release builds, and when this happens, one may have to resort to more primitive forms of debugging. 

So you and your printf are now on your own in the search for a line of code that causes the release build to crash. Still you are lucky: adding printf statements to this program affects neither the bug (it still crashes at the same original code line) nor the execution time (at least not notably). So even the naive approach of putting a printf statement before each line, running the program until it crashes, and checking the last printed line, would work.

However, it takes some time to add each printf statement to the code, and the program may have a lot of lines. So perhaps a better plan would involve putting a printf statement in the middle of the program, letting it run, seeing whether it crashes before the added line, and then continuing the search in either the first or second half of the code.

But then again, running the program may take a lot of time, so the most time-efficient strategy might be something in between. Write a program that computes the minimum worst-case time to find the crashing line (no matter where it is), assuming you choose an optimal strategy for placing your printf statements.

We’re releasing the new version in five hours, so this issue is escalated and needs to be fixed ASAP.

-----Input-----
The input consists of one line with three integers:
 - $n$ ($1 \le n \le 10^6$), the number of code lines;
 - $r$ ($1 \le r \le 10^9$), the amount of time it takes to compile and run the program until it crashes;
 - $p$ ($1 \le p \le 10^9$), the time it takes to add a single printf line.

You have already run the program once and therefore already know that it does crash somewhere.

-----Output-----
Output the worst-case time to find the crashing line when using an optimal strategy.

-----Examples-----
Sample Input 1:
1 100 20
Sample Output 1:
0

Sample Input 2:
10 10 1
Sample Output 2:
19

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