vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Let's denote as L(x, p) an infinite sequence of integers y such that gcd(p, y) = 1 and y > x (where gcd is the greatest common divisor of two integer numbers), sorted in ascending order. The elements of L(x, p) are 1-indexed; for example, 9, 13 and 15 are the first, the second and the third elements of L(7, 22), respectively.

You have to process t queries. Each query is denoted by three integers x, p and k, and the answer to this query is k-th element of L(x, p).


-----Input-----

The first line contains one integer t (1 ≤ t ≤ 30000) — the number of queries to process.

Then t lines follow. i-th line contains three integers x, p and k for i-th query (1 ≤ x, p, k ≤ 10^6).


-----Output-----

Print t integers, where i-th integer is the answer to i-th query.


-----Examples-----
Input
3
7 22 1
7 22 2
7 22 3

Output
9
13
15

Input
5
42 42 42
43 43 43
44 44 44
45 45 45
46 46 46

Output
187
87
139
128
141

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Momiji has got a rooted tree, consisting of *n* nodes. The tree nodes are numbered by integers from 1 to *n*. The root has number 1. Momiji decided to play a game on this tree.

The game consists of several steps. On each step, Momiji chooses one of the remaining tree nodes (let's denote it by *v*) and removes all the subtree nodes with the root in node *v* from the tree. Node *v* gets deleted as well. The game finishes when the tree has no nodes left. In other words, the game finishes after the step that chooses the node number 1.

Each time Momiji chooses a new node uniformly among all the remaining nodes. Your task is to find the expectation of the number of steps in the described game.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105) — the number of nodes in the tree. The next *n*<=-<=1 lines contain the tree edges. The *i*-th line contains integers *a**i*, *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*; *a**i*<=≠<=*b**i*) — the numbers of the nodes that are connected by the *i*-th edge.

It is guaranteed that the given graph is a tree.

Output Specification:
Print a single real number — the expectation of the number of steps in the described game.

The answer will be considered correct if the absolute or relative error doesn't exceed 10<=-<=6.

Demo Input:
['2\n1 2\n', '3\n1 2\n1 3\n']

Demo Output:
['1.50000000000000000000\n', '2.00000000000000000000\n']

Note:
In the first sample, there are two cases. One is directly remove the root and another is remove the root after one step. Thus the expected steps are: 

In the second sample, things get more complex. There are two cases that reduce to the first sample, and one case cleaned at once. Thus the expected steps are:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
start() & end()

These expressions return the indices of the start and end of the substring matched by the group.

Code  

>>> import re
>>> m = re.search(r'\d+','1234')
>>> m.end()
4
>>> m.start()
0

Task 

You are given a string $\mbox{S}$. 

Your task is to find the indices of the start and end of string $\boldsymbol{k}$ in $\mbox{S}$.

Input Format

The first line contains the string $\mbox{S}$. 

The second line contains the string $\boldsymbol{k}$.

Constraints  

$0<len(S)<100$ 

$0<len(k)<len(S)$

Output Format

Print the tuple in this format: (start _index, end _index). 

If no match is found, print (-1, -1).

Sample Input
aaadaa
aa

Sample Output
(0, 1)  
(1, 2)
(4, 5)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A bus moves along the coordinate line Ox from the point x = 0 to the point x = a. After starting from the point x = 0, it reaches the point x = a, immediately turns back and then moves to the point x = 0. After returning to the point x = 0 it immediately goes back to the point x = a and so on. Thus, the bus moves from x = 0 to x = a and back. Moving from the point x = 0 to x = a or from the point x = a to x = 0 is called a bus journey. In total, the bus must make k journeys.

The petrol tank of the bus can hold b liters of gasoline. To pass a single unit of distance the bus needs to spend exactly one liter of gasoline. The bus starts its first journey with a full petrol tank.

There is a gas station in point x = f. This point is between points x = 0 and x = a. There are no other gas stations on the bus route. While passing by a gas station in either direction the bus can stop and completely refuel its tank. Thus, after stopping to refuel the tank will contain b liters of gasoline.

What is the minimum number of times the bus needs to refuel at the point x = f to make k journeys? The first journey starts in the point x = 0.


-----Input-----

The first line contains four integers a, b, f, k (0 < f < a ≤ 10^6, 1 ≤ b ≤ 10^9, 1 ≤ k ≤ 10^4) — the endpoint of the first bus journey, the capacity of the fuel tank of the bus, the point where the gas station is located, and the required number of journeys.


-----Output-----

Print the minimum number of times the bus needs to refuel to make k journeys. If it is impossible for the bus to make k journeys, print -1.


-----Examples-----
Input
6 9 2 4

Output
4

Input
6 10 2 4

Output
2

Input
6 5 4 3

Output
-1



-----Note-----

In the first example the bus needs to refuel during each journey.

In the second example the bus can pass 10 units of distance without refueling. So the bus makes the whole first journey, passes 4 units of the distance of the second journey and arrives at the point with the gas station. Then it can refuel its tank, finish the second journey and pass 2 units of distance from the third journey. In this case, it will again arrive at the point with the gas station. Further, he can refill the tank up to 10 liters to finish the third journey and ride all the way of the fourth journey. At the end of the journey the tank will be empty. 

In the third example the bus can not make all 3 journeys because if it refuels during the second journey, the tanks will contain only 5 liters of gasoline, but the bus needs to pass 8 units of distance until next refueling.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Amr loves Chemistry, and specially doing experiments. He is preparing for a new interesting experiment.

Amr has *n* different types of chemicals. Each chemical *i* has an initial volume of *a**i* liters. For this experiment, Amr has to mix all the chemicals together, but all the chemicals volumes must be equal first. So his task is to make all the chemicals volumes equal.

To do this, Amr can do two different kind of operations. 
 -  Choose some chemical *i* and double its current volume so the new volume will be 2*a**i* -  Choose some chemical *i* and divide its volume by two (integer division) so the new volume will be  
Suppose that each chemical is contained in a vessel of infinite volume. Now Amr wonders what is the minimum number of operations required to make all the chemicals volumes equal?

Input Specification:
The first line contains one number *n* (1<=≤<=*n*<=≤<=105), the number of chemicals.

The second line contains *n* space separated integers *a**i* (1<=≤<=*a**i*<=≤<=105), representing the initial volume of the *i*-th chemical in liters.

Output Specification:
Output one integer the minimum number of operations required to make all the chemicals volumes equal.

Demo Input:
['3\n4 8 2\n', '3\n3 5 6\n']

Demo Output:
['2', '5']

Note:
In the first sample test, the optimal solution is to divide the second chemical volume by two, and multiply the third chemical volume by two to make all the volumes equal 4.

In the second sample test, the optimal solution is to divide the first chemical volume by two, and divide the second and the third chemical volumes by two twice to make all the volumes equal 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan wants to make a necklace as a present to his beloved girl. A necklace is a cyclic sequence of beads of different colors. Ivan says that necklace is beautiful relative to the cut point between two adjacent beads, if the chain of beads remaining after this cut is a palindrome (reads the same forward and backward).

<image>

Ivan has beads of n colors. He wants to make a necklace, such that it's beautiful relative to as many cuts as possible. He certainly wants to use all the beads. Help him to make the most beautiful necklace.

Input

The first line of the input contains a single number n (1 ≤ n ≤ 26) — the number of colors of beads. The second line contains after n positive integers ai — the quantity of beads of i-th color. It is guaranteed that the sum of ai is at least 2 and does not exceed 100 000.

Output

In the first line print a single number — the maximum number of beautiful cuts that a necklace composed from given beads may have. In the second line print any example of such necklace.

Each color of the beads should be represented by the corresponding lowercase English letter (starting with a). As the necklace is cyclic, print it starting from any point.

Examples

Input

3
4 2 1


Output

1
abacaba

Input

1
4


Output

4
aaaa


Input

2
1 1


Output

0
ab

Note

In the first sample a necklace can have at most one beautiful cut. The example of such a necklace is shown on the picture.

In the second sample there is only one way to compose a necklace.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya plays the Plane of Tanks. The tanks in this game keep trying to finish each other off. But your "Pedalny" is not like that... He just needs to drive in a straight line from point A to point B on the plane. Unfortunately, on the same plane are n enemy tanks. We shall regard all the tanks as points. At the initial moment of time Pedalny is at the point A. Enemy tanks would be happy to destroy it immediately, but initially their turrets are tuned in other directions. Specifically, for each tank we know the initial rotation of the turret ai (the angle in radians relative to the OX axis in the counterclockwise direction) and the maximum speed of rotation of the turret wi (radians per second). If at any point of time a tank turret will be aimed precisely at the tank Pedalny, then the enemy fires and it never misses. Pedalny can endure no more than k shots. Gun reloading takes very much time, so we can assume that every enemy will produce no more than one shot. Your task is to determine what minimum speed of v Pedalny must have to get to the point B. It is believed that Pedalny is able to instantly develop the speed of v, and the first k shots at him do not reduce the speed and do not change the coordinates of the tank.

Input

The first line contains 4 numbers – the coordinates of points A and B (in meters), the points do not coincide. On the second line number n is given (1 ≤ n ≤ 104). It is the number of enemy tanks. Each of the following n lines contain the coordinates of a corresponding tank xi, yi and its parameters ai and wi (0 ≤ ai ≤ 2π, 0 ≤ wi ≤ 100). Numbers ai and wi contain at most 5 digits after the decimal point. All coordinates are integers and their absolute values do not exceed 105. Enemy tanks can rotate a turret in the clockwise as well as in the counterclockwise direction at the angular speed of not more than wi. It is guaranteed that each of the enemy tanks will need at least 0.1 seconds to aim at any point of the segment AB and each of the enemy tanks is posistioned no closer than 0.1 meters to line AB. On the last line is given the number k (0 ≤ k ≤ n).

Output

Print a single number with absolute or relative error no more than 10 - 4 — the minimum required speed of Pedalny in meters per second.

Examples

Input

0 0 10 0
1
5 -5 4.71238 1
0


Output

4.2441


Input

0 0 10 0
1
5 -5 4.71238 1
1


Output

0.0000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
 

Find out how many ways to assign symbols to make sum of integers equal to target S.  


Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.



Note:

The length of the given array is positive and will not exceed 20. 
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mandarin chinese
, Russian and Vietnamese as well.
Chef is organising a contest with $P$ problems (numbered $1$ through $P$). Each problem has $S$ subtasks (numbered $1$ through $S$).
The difficulty of a problem can be calculated as follows:
- Let's denote the score of the $k$-th subtask of this problem by $SC_k$ and the number of contestants who solved it by $NS_k$.
- Consider the subtasks sorted in the order of increasing score.
- Calculate the number $n$ of valid indices $k$ such that $NS_k > NS_{k + 1}$.
- For problem $i$, the difficulty is a pair of integers $(n, i)$.
You should sort the problems in the increasing order of difficulty levels. Since difficulty level is a pair, problem $a$ is more difficult than problem $b$ if the number $n$ is greater for problem $a$ than for problem $b$, or if $a > b$ and $n$ is the same for problems $a$ and $b$.

-----Input-----
- The first line of the input contains two space-separated integers $P$ and $S$ denoting the number of problems and the number of subtasks in each problem.
- $2P$ lines follow. For each valid $i$, the $2i-1$-th of these lines contains $S$ space-separated integers $SC_1, SC_2, \dots, SC_S$ denoting the scores of the $i$-th problem's subtasks, and the $2i$-th of these lines contains $S$ space-separated integers $NS_1, NS_2, \dots, NS_S$ denoting the number of contestants who solved the $i$-th problem's subtasks.

-----Output-----
Print $P$ lines containing one integer each — the indices of the problems in the increasing order of difficulty.

-----Constraints-----
- $1 \le P \le 100,000$
- $2 \le S \le 30$
- $1 \le SC_i \le 100$ for each valid $i$
- $1 \le NS_i \le 1,000$ for each valid $i$
- in each problem, the scores of all subtasks are unique

-----Subtasks-----
Subtask #1 (25 points): $S = 2$
Subtask #2 (75 points): original constraints

-----Example Input-----
3 3
16 24 60
498 861 589
14 24 62
72 557 819
16 15 69
435 779 232

-----Example Output-----
2
1
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are a lot of things which could be cut — trees, paper, "the rope". In this problem you are going to cut a sequence of integers.

There is a sequence of integers, which contains the equal number of even and odd numbers. Given a limited budget, you need to make maximum possible number of cuts such that each resulting segment will have the same number of odd and even integers.

Cuts separate a sequence to continuous (contiguous) segments. You may think about each cut as a break between two adjacent elements in a sequence. So after cutting each element belongs to exactly one segment. Say, $[4, 1, 2, 3, 4, 5, 4, 4, 5, 5]$ $\to$ two cuts $\to$ $[4, 1 | 2, 3, 4, 5 | 4, 4, 5, 5]$. On each segment the number of even elements should be equal to the number of odd elements.

The cost of the cut between $x$ and $y$ numbers is $|x - y|$ bitcoins. Find the maximum possible number of cuts that can be made while spending no more than $B$ bitcoins.


-----Input-----

First line of the input contains an integer $n$ ($2 \le n \le 100$) and an integer $B$ ($1 \le B \le 100$) — the number of elements in the sequence and the number of bitcoins you have.

Second line contains $n$ integers: $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 100$) — elements of the sequence, which contains the equal number of even and odd numbers


-----Output-----

Print the maximum possible number of cuts which can be made while spending no more than $B$ bitcoins.


-----Examples-----
Input
6 4
1 2 5 10 15 20

Output
1

Input
4 10
1 3 2 4

Output
0

Input
6 100
1 2 3 4 5 6

Output
2



-----Note-----

In the first sample the optimal answer is to split sequence between $2$ and $5$. Price of this cut is equal to $3$ bitcoins.

In the second sample it is not possible to make even one cut even with unlimited number of bitcoins.

In the third sample the sequence should be cut between $2$ and $3$, and between $4$ and $5$. The total price of the cuts is $1 + 1 = 2$ bitcoins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The war is going on between star world and dark world. The king of the starworld need to choose troops of soldiers and send them for war. There are two type of soldiers 1 and 0. He can choose atmost  k troops and in each troop he can choose consecutive s soldiers from the soldiers who are standing in a row.

Now the problem is soldier of 1 type is more powerful than 0. so he wanted to maximize no. of soldiers having type 1.  

Help him to find maximum number of soldiers having type 1.

Input :
first line contains T- no. of test cases.
In each test case first line contains three space separated integers n , k ans s - no. of soldiers , no. of troops , consecutive soldiers in each troop.
Third line contains n space separated integers indicating type of soldier 0 or 1.

Output :
Print maximum number of soldiers of 1 type he is able to choose. 

Constraints :
1≤ T ,s ,n, k  ≤10^3
1≤ sum of n/s over all test cases ≤10^4

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

SAMPLE OUTPUT
4
3
3
3
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is planning a huge party for all of you and has ordered M pizzas. He wants to invite as many people to the party. However, he knows that everyone will have exactly one slice of a pizza (regardless of the size) and he wants to make sure that he has enough pizza slices. 
Chef is very lazy and will only make a total of N straight cuts among all the pizzas. Each pizza is also of different size and to avoid the slices getting too small the chef can only make a max of Ai cuts to the ith pizza. He wants to maximize the number of slices of pizza. Since chef is busy with preparing other aspects of the party he wants you to find out the maximum number of slices he can get following the constraints. 
If a pizza is not cut at all then it is considered as 1 slice.  

-----Input-----
First line contains two integers M and N.
The second line of input contains the array A.

-----Output-----
Output a single integer - the maximum number of slices chef can get.

-----Constraints-----
- 1 ≤ M ≤ 2*105
- 1 ≤ N,Ai ≤ 2*105

-----Subtasks-----
- Subtask 1: 1 ≤ M,N ≤ 100 - 10 points 
- Subtask 2: 1 ≤ N ≤ 100, 
1 ≤ M ≤ 105 - 20 points
- Subtask 3: Original Constraints - 70 points

-----Example-----
Input:
5 10
1 2 3 4 5
Output:
31

-----Explanation-----
Example case 1. One of the optimal way to cut would be to do {0, 1,  0, 4, 5} cuts.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your friend gives you an equation A≡X2(modM) and asks you to find an integer solution for X.

However, you know your friend's mischievous nature and suspect that there is no solution to such an equation. Thus, you first want to find out whether there is a solution to it.

You may find this link helpful: http://en.wikipedia.org/wiki/Euler%27s_criterion

Input Format

The first line contains the number of cases, T. T lines follow, each containing two integers A and M separated by a single space.

Output Format

Output T lines, each containing one word: YES, if a solution exists and NO otherwise.

Constraints

0<T≤105
2≤M<109, M is prime
0≤A<M

SAMPLE INPUT
2  
5 7  
4 7

SAMPLE OUTPUT
NO  
YES

Explanation

Explanation

In the second test case, we can take X=2, as 4≡22(mod7). Or we can take X=5, as 52=25≡4(mod7).

However there is no integer which gives 5 modulo 7 when squared.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarpus develops an interesting theory about the interrelation of arithmetic progressions with just everything in the world. His current idea is that the population of the capital of Berland changes over time like an arithmetic progression. Well, or like multiple arithmetic progressions.

Polycarpus believes that if he writes out the population of the capital for several consecutive years in the sequence a_1, a_2, ..., a_{n}, then it is convenient to consider the array as several arithmetic progressions, written one after the other. For example, sequence (8, 6, 4, 2, 1, 4, 7, 10, 2) can be considered as a sequence of three arithmetic progressions (8, 6, 4, 2), (1, 4, 7, 10) and (2), which are written one after another.

Unfortunately, Polycarpus may not have all the data for the n consecutive years (a census of the population doesn't occur every year, after all). For this reason, some values of a_{i} ​​may be unknown. Such values are represented by number -1.

For a given sequence a = (a_1, a_2, ..., a_{n}), which consists of positive integers and values ​​-1, find the minimum number of arithmetic progressions Polycarpus needs to get a. To get a, the progressions need to be written down one after the other. Values ​​-1 may correspond to an arbitrary positive integer and the values a_{i} > 0 must be equal to the corresponding elements of sought consecutive record of the progressions.

Let us remind you that a finite sequence c is called an arithmetic progression if the difference c_{i} + 1 - c_{i} of any two consecutive elements in it is constant. By definition, any sequence of length 1 is an arithmetic progression.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 2·10^5) — the number of elements in the sequence. The second line contains integer values a_1, a_2, ..., a_{n} separated by a space (1 ≤ a_{i} ≤ 10^9 or a_{i} =  - 1).


-----Output-----

Print the minimum number of arithmetic progressions that you need to write one after another to get sequence a. The positions marked as -1 in a can be represented by any positive integers.


-----Examples-----
Input
9
8 6 4 2 1 4 7 10 2

Output
3

Input
9
-1 6 -1 2 -1 4 7 -1 2

Output
3

Input
5
-1 -1 -1 -1 -1

Output
1

Input
7
-1 -1 4 5 1 2 3

Output
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given an integer `n` and your task will be to return `the largest integer that is <= n and has the highest digit sum`.

For example:
```
solve(100) = 99. Digit Sum for 99 = 9 + 9 = 18. No other number <= 100 has a higher digit sum.
solve(10) = 9
solve(48) = 48. Note that 39 is also an option, but 48 is larger.
```

Input range is `0 < n < 1e11`

More examples in the test cases.

Good luck!

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