vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Koala Land consists of m bidirectional roads connecting n cities. The roads are numbered from 1 to m by order in input. It is guaranteed, that one can reach any city from every other city.

Koala starts traveling from city 1. Whenever he travels on a road, he writes its number down in his notebook. He doesn't put spaces between the numbers, so they all get concatenated into a single number.

Before embarking on his trip, Koala is curious about the resulting number for all possible destinations. For each possible destination, what is the smallest number he could have written for it?

Since these numbers may be quite large, print their remainders modulo 10^9+7. Please note, that you need to compute the remainder of the minimum possible number, not the minimum possible remainder.

Input

The first line contains two integers n and m (2 ≤ n ≤ 10^5, n - 1 ≤ m ≤ 10^5), the number of cities and the number of roads, respectively.

The i-th of the following m lines contains integers x_i and y_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i), representing a bidirectional road between cities x_i and y_i.

It is guaranteed, that for any pair of cities there is at most one road connecting them, and that one can reach any city from every other city. 

Output

Print n - 1 integers, the answer for every city except for the first city.

The i-th integer should be equal to the smallest number he could have written for destination i+1. Since this number may be large, output its remainder modulo 10^9+7.

Examples

Input


11 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11


Output


1
12
123
1234
12345
123456
1234567
12345678
123456789
345678826


Input


12 19
1 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 11
11 12
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10


Output


1
12
13
14
15
16
17
18
19
1210
121011


Input


12 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 3
1 4
1 10


Output


1
12
13
134
1345
13456
1498
149
14
1410
141011

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array A of non-negative integers, return the maximum sum of elements in two non-overlapping (contiguous) subarrays, which have lengths L and M.  (For clarification, the L-length subarray could occur before or after the M-length subarray.)
Formally, return the largest V for which V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) and either:

0 <= i < i + L - 1 < j < j + M - 1 < A.length, or
0 <= j < j + M - 1 < i < i + L - 1 < A.length.

 



Example 1:
Input: A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
Output: 20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.


Example 2:
Input: A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
Output: 29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.


Example 3:
Input: A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
Output: 31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [3,8] with length 3.

 
Note:

L >= 1
M >= 1
L + M <= A.length <= 1000
0 <= A[i] <= 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Now that Chef has finished baking and frosting his cupcakes, it's time to package them. Chef has N cupcakes, and needs to decide how many cupcakes to place in each package. Each package must contain the same number of cupcakes. Chef will choose an integer A between 1 and N, inclusive, and place exactly A cupcakes into each package.  Chef makes as many packages as possible. Chef then gets to eat the remaining cupcakes. Chef enjoys eating cupcakes very much. Help Chef choose the package size A that will let him eat as many cupcakes as possible.

-----Input-----

Input begins with an integer T, the number of test cases. Each test case consists of a single integer N, the number of cupcakes.

-----Output-----

For each test case, output the package size that will maximize the number of leftover cupcakes. If multiple package sizes will result in the same number of leftover cupcakes, print the largest such size.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 2 ≤ N ≤ 100000000 (108)

-----Sample Input-----
2
2
5

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

-----Explanation-----

In the first test case, there will be no leftover cupcakes regardless of the size Chef chooses, so he chooses the largest possible size.  In the second test case, there will be 2 leftover cupcakes.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have an array of positive integers *a*[1],<=*a*[2],<=...,<=*a*[*n*] and a set of bad prime numbers *b*1,<=*b*2,<=...,<=*b**m*. The prime numbers that do not occur in the set *b* are considered good. The beauty of array *a* is the sum , where function *f*(*s*) is determined as follows:
 -  *f*(1)<==<=0; -  Let's assume that *p* is the minimum prime divisor of *s*. If *p* is a good prime, then , otherwise . 
You are allowed to perform an arbitrary (probably zero) number of operations to improve array *a*. The operation of improvement is the following sequence of actions:
 -  Choose some number *r* (1<=≤<=*r*<=≤<=*n*) and calculate the value *g* = GCD(*a*[1],<=*a*[2],<=...,<=*a*[*r*]). -  Apply the assignments: , , ..., . 
What is the maximum beauty of the array you can get?

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=5000) showing how many numbers are in the array and how many bad prime numbers there are.

The second line contains *n* space-separated integers *a*[1],<=*a*[2],<=...,<=*a*[*n*] (1<=≤<=*a*[*i*]<=≤<=109) — array *a*. The third line contains *m* space-separated integers *b*1,<=*b*2,<=...,<=*b**m* (2<=≤<=*b*1<=&lt;<=*b*2<=&lt;<=...<=&lt;<=*b**m*<=≤<=109) — the set of bad prime numbers.

Output Specification:
Print a single integer — the answer to the problem.

Demo Input:
['5 2\n4 20 34 10 10\n2 5\n', '4 5\n2 4 8 16\n3 5 7 11 17\n']

Demo Output:
['-2\n', '10\n']

Note:
Note that the answer to the problem can be negative.

The GCD(*x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*k*</sub>) is the maximum positive integer that divides each *x*<sub class="lower-index">*i*</sub>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Unfortunately someone has come and eaten the problem statement. Are you good enough to solve it without the statement?

Input
The first line contains T denoting the number of test cases.
The next  T lines describe test cases and contain two integers each: N and M.

Output
For each test case output one integer - answer for the question.

Constraints
T ≤ 1000
1 ≤ N, M ≤ 10^9

Note:
N, M ≤ 1000 for 30% of the test

SAMPLE INPUT
6
28 1
39 1
90 1
15 2
123 2
114514 1919

SAMPLE OUTPUT
68
90
81
40
17
16

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Iahub wants to enhance his multitasking abilities. In order to do this, he wants to sort *n* arrays simultaneously, each array consisting of *m* integers.

Iahub can choose a pair of distinct indices *i* and *j* (1<=≤<=*i*,<=*j*<=≤<=*m*,<=*i*<=≠<=*j*). Then in each array the values at positions *i* and *j* are swapped only if the value at position *i* is strictly greater than the value at position *j*.

Iahub wants to find an array of pairs of distinct indices that, chosen in order, sort all of the *n* arrays in ascending or descending order (the particular order is given in input). The size of the array can be at most  (at most  pairs). Help Iahub, find any suitable array.

Input Specification:
The first line contains three integers *n* (1<=≤<=<=*n*<=≤<=1000), *m* (1<=≤<=*m*<=≤<=<=100) and *k*. Integer *k* is 0 if the arrays must be sorted in ascending order, and 1 if the arrays must be sorted in descending order. Each line *i* of the next *n* lines contains *m* integers separated by a space, representing the *i*-th array. For each element *x* of the array *i*, 1<=≤<=*x*<=≤<=106 holds.

Output Specification:
On the first line of the output print an integer *p*, the size of the array (*p* can be at most ). Each of the next *p* lines must contain two distinct integers *i* and *j* (1<=≤<=*i*,<=*j*<=≤<=*m*,<=*i*<=≠<=*j*), representing the chosen indices.

If there are multiple correct answers, you can print any.

Demo Input:
['2 5 0\n1 3 2 5 4\n1 4 3 2 5\n', '3 2 1\n1 2\n2 3\n3 4\n']

Demo Output:
['3\n2 4\n2 3\n4 5\n', '1\n2 1\n']

Note:
Consider the first sample. After the first operation, the arrays become [1, 3, 2, 5, 4] and [1, 2, 3, 4, 5]. After the second operation, the arrays become [1, 2, 3, 5, 4] and [1, 2, 3, 4, 5]. After the third operation they become [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In 2012, human beings have been exposed to fierce onslaught of unidentified mysterious extra-terrestrial creatures. We have exhaused because of the long war and can't regist against them any longer. Only you, an excellent wizard, can save us. Yes, it's time to stand up!

The enemies are dispatched to the earth with being aligned like an n * n square. Appearently some of them have already lost their fighting capabilities for some unexpected reason. You have invented a highest grade magic spell 'MYON' to defeat them all. An attack of this magic covers any rectangles (which is parallel to axis). Once you cast a spell "myon," then all the enemies which the magic covers will lose their fighting capabilities because of tremendous power of the magic. However, the magic seems to activate enemies' self-repairing circuit. Therefore if any enemy which have already lost its fighting capability is exposed to the magic, the enemy repossesses its fighting capability. You will win the war when all the enemies will lose their fighting capabilities.

Let me show an example. An array of enemies below have dispatched:


1 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 1 1


Here, '0' means an enemy that doesn't possess fighting capability, and '1' means an enemy that possesses. First, you cast a spell "myon" with covering all the enemies, which results in;


0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0


Next, cast once again with covering central 3 * 3 enemies.


0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0


Now you can defeat them all by casting a spell covers remaining one. Therefore you can cast "myonmyonmyon," which is the shortest spell for this case.

You are given the information of the array. Please write a program that generates the shortest spell that can defeat them all.

Constraints

* 1 ≤ n ≤ 5

Input

The first line of each test case has an integer n. Following n lines are information of an array of enemies. The format is same as described in the problem statement.

Input terminates when n = 0. You may assume that one or more enemy have fighting capability.

Output

For each dataset, output the shortest spell.

Example

Input

5
1 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 1 1
3
1 1 1
1 1 1
1 1 1
5
1 1 1 1 0
1 1 1 1 0
1 0 0 0 1
0 1 1 1 1
0 1 1 1 1
0


Output

myonmyonmyon
myon
myonmyon

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We call a string good, if after merging all the consecutive equal characters, the resulting string is palindrome. For example, "aabba" is good, because after the merging step it will become "aba".

Given a string, you have to find two values:  the number of good substrings of even length;  the number of good substrings of odd length. 


-----Input-----

The first line of the input contains a single string of length n (1 ≤ n ≤ 10^5). Each character of the string will be either 'a' or 'b'.


-----Output-----

Print two space-separated integers: the number of good substrings of even length and the number of good substrings of odd length.


-----Examples-----
Input
bb

Output
1 2

Input
baab

Output
2 4

Input
babb

Output
2 5

Input
babaa

Output
2 7



-----Note-----

In example 1, there are three good substrings ("b", "b", and "bb"). One of them has even length and two of them have odd length.

In example 2, there are six good substrings (i.e. "b", "a", "a", "b", "aa", "baab"). Two of them have even length and four of them have odd length.

In example 3, there are seven good substrings (i.e. "b", "a", "b", "b", "bb", "bab", "babb"). Two of them have even length and five of them have odd length.

Definitions

A substring s[l, r] (1 ≤ l ≤ r ≤ n) of string s = s_1s_2... s_{n} is string s_{l}s_{l} + 1... s_{r}.

A string s = s_1s_2... s_{n} is a palindrome if it is equal to string s_{n}s_{n} - 1... s_1.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Recall that the bracket sequence is considered regular if it is possible to insert symbols '+' and '1' into it so that the result is a correct arithmetic expression. For example, a sequence "(()())" is regular, because we can get correct arithmetic expression insering symbols '+' and '1': "((1+1)+(1+1))". Also the following sequences are regular: "()()()", "(())" and "()". The following sequences are not regular bracket sequences: ")(", "(()" and "())(()".

In this problem you are given two integers *n* and *k*. Your task is to construct a regular bracket sequence consisting of round brackets with length 2·*n* with total sum of nesting of all opening brackets equals to exactly *k*. The nesting of a single opening bracket equals to the number of pairs of brackets in which current opening bracket is embedded.

For example, in the sequence "()(())" the nesting of first opening bracket equals to 0, the nesting of the second opening bracket equals to 0 and the nesting of the third opening bracket equal to 1. So the total sum of nestings equals to 1.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*n*<=≤<=3·105, 0<=≤<=*k*<=≤<=1018) — the number of opening brackets and needed total nesting.

Output Specification:
Print the required regular bracket sequence consisting of round brackets.

If there is no solution print "Impossible" (without quotes).

Demo Input:
['3 1\n', '4 6\n', '2 5\n']

Demo Output:
['()(())', '(((())))', 'Impossible\n']

Note:
The first example is examined in the statement.

In the second example the answer is "(((())))". The nesting of the first opening bracket is 0, the nesting of the second is 1, the nesting of the third is 2, the nesting of fourth is 3. So the total sum of nestings equals to 0 + 1 + 2 + 3 = 6.

In the third it is impossible to construct a regular bracket sequence, because the maximum possible total sum of nestings for two opening brackets equals to 1. This total sum of nestings is obtained for the sequence "(())".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
$N$ points are placed in the coordinate plane.

Write a program that calculates how many ways we can choose three points so that they form a right triangle with legs parallel to the coordinate axes.

A right triangle has one 90-degree internal angle. The legs of a right triangle are its two shorter sides.

-----Input-----
The first line of input contains the integer $N$ ($3 \le N \le 100000$), the number of points.

Each of the following $N$ lines contains two integers $X$ and $Y$ ($1 \le X, Y \le 100000$), the coordinates of one point.

No pair of points will share the same pair of coordinates.

-----Output-----
Output the number of triangles.

-----Examples-----
Sample Input 1:
3
4 2
2 1
1 3
Sample Output 1:
0

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two strings $s$ and $t$ both of length $2$ and both consisting only of characters 'a', 'b' and 'c'.

Possible examples of strings $s$ and $t$: "ab", "ca", "bb".

You have to find a string $res$ consisting of $3n$ characters, $n$ characters should be 'a', $n$ characters should be 'b' and $n$ characters should be 'c' and $s$ and $t$ should not occur in $res$ as substrings.

A substring of a string is a contiguous subsequence of that string. So, the strings "ab", "ac" and "cc" are substrings of the string "abacc", but the strings "bc", "aa" and "cb" are not substrings of the string "abacc".

If there are multiple answers, you can print any of them.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 10^5$) — the number of characters 'a', 'b' and 'c' in the resulting string.

The second line of the input contains one string $s$ of length $2$ consisting of characters 'a', 'b' and 'c'.

The third line of the input contains one string $t$ of length $2$ consisting of characters 'a', 'b' and 'c'.


-----Output-----

If it is impossible to find the suitable string, print "NO" on the first line. 

Otherwise print "YES" on the first line and string $res$ on the second line. $res$ should consist of $3n$ characters, $n$ characters should be 'a', $n$ characters should be 'b' and $n$ characters should be 'c' and $s$ and $t$ should not occur in $res$ as substrings.

If there are multiple answers, you can print any of them.


-----Examples-----
Input
2
ab
bc

Output
YES
acbbac

Input
3
aa
bc

Output
YES
cacbacbab

Input
1
cb
ac

Output
YES
abc

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
N different natural numbers are given. If you select four different ones and set them as $ A $, $ B $, $ C $, $ D $, the following formula

$ \ Frac {A + B} {C --D} $



I want to find the maximum value of.




Given N different natural numbers, choose 4 different from them and create a program to find the maximum value of the above formula.



Input

The input is given in the following format.


N
a1 a2 ... aN


The number N (4 ≤ N ≤ 1000) of natural numbers is given in the first line. The value ai (1 ≤ ai ≤ 108) of each natural number is given in the second line. However, the same natural number does not appear more than once (ai ≠ aj for i ≠ j).

Output

Outputs the maximum value of the above formula as a real number for a given N natural numbers. However, the error must not exceed plus or minus 10-5.

Examples

Input

10
1 2 3 4 5 6 7 8 9 10


Output

19.00000


Input

5
22 100 42 3 86


Output

9.78947


Input

6
15 21 36 10 34 5


Output

18.00000


Input

4
100000 99999 8 1


Output

28571.285714

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a$, consisting of $n$ positive integers.

Let's call a concatenation of numbers $x$ and $y$ the number that is obtained by writing down numbers $x$ and $y$ one right after another without changing the order. For example, a concatenation of numbers $12$ and $3456$ is a number $123456$.

Count the number of ordered pairs of positions $(i, j)$ ($i \neq j$) in array $a$ such that the concatenation of $a_i$ and $a_j$ is divisible by $k$.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $2 \le k \le 10^9$).

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


-----Output-----

Print a single integer — the number of ordered pairs of positions $(i, j)$ ($i \neq j$) in array $a$ such that the concatenation of $a_i$ and $a_j$ is divisible by $k$.


-----Examples-----
Input
6 11
45 1 10 12 11 7

Output
7

Input
4 2
2 78 4 10

Output
12

Input
5 2
3 7 19 3 3

Output
0



-----Note-----

In the first example pairs $(1, 2)$, $(1, 3)$, $(2, 3)$, $(3, 1)$, $(3, 4)$, $(4, 2)$, $(4, 3)$ suffice. They produce numbers $451$, $4510$, $110$, $1045$, $1012$, $121$, $1210$, respectively, each of them is divisible by $11$.

In the second example all $n(n - 1)$ pairs suffice.

In the third example no pair is sufficient.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* lights aligned in a row. These lights are numbered 1 to *n* from left to right. Initially some of the lights are switched on. Shaass wants to switch all the lights on. At each step he can switch a light on (this light should be switched off at that moment) if there's at least one adjacent light which is already switched on. 

He knows the initial state of lights and he's wondering how many different ways there exist to switch all the lights on. Please find the required number of ways modulo 1000000007 (109<=+<=7).

Input Specification:
The first line of the input contains two integers *n* and *m* where *n* is the number of lights in the sequence and *m* is the number of lights which are initially switched on, (1<=≤<=*n*<=≤<=1000,<=1<=≤<=*m*<=≤<=*n*). The second line contains *m* distinct integers, each between 1 to *n* inclusive, denoting the indices of lights which are initially switched on.

Output Specification:
In the only line of the output print the number of different possible ways to switch on all the lights modulo 1000000007 (109<=+<=7).

Demo Input:
['3 1\n1\n', '4 2\n1 4\n', '11 2\n4 8\n']

Demo Output:
['1\n', '2\n', '6720\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In your class, you have started lessons about geometric progression.
Since you are also a programmer, you have decided to write a function that will print first `n` elements of the sequence with the given constant `r` and first element `a`.

Result should be separated by comma and space.

### Example

```python
geometric_sequence_elements(2, 3, 5) == '2, 6, 18, 54, 162'
```

More info: https://en.wikipedia.org/wiki/Geometric_progression

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has $N$ axis-parallel rectangles in a 2D Cartesian coordinate system. These rectangles may intersect, but it is guaranteed that all their $4N$ vertices are pairwise distinct.
Unfortunately, Chef lost one vertex, and up until now, none of his fixes have worked (although putting an image of a point on a milk carton might not have been the greatest idea after all…). Therefore, he gave you the task of finding it! You are given the remaining $4N-1$ points and you should find the missing one.

-----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 a single integer $N$.
- Then, $4N-1$ lines follow. Each of these lines contains two space-separated integers $x$ and $y$ denoting a vertex $(x, y)$ of some rectangle.

-----Output-----
For each test case, print a single line containing two space-separated integers $X$ and $Y$ ― the coordinates of the missing point. It can be proved that the missing point can be determined uniquely.

-----Constraints-----
- $T \le 100$
- $1 \le N \le 2 \cdot 10^5$
- $|x|, |y| \le 10^9$
- the sum of $N$ over all test cases does not exceed $2 \cdot 10^5$

-----Subtasks-----
Subtask #1 (20 points):
- $T = 5$
- $N \le 20$
Subtask #2 (30 points): $|x|, |y| \le 10^5$
Subtask #3 (50 points): original constraints

-----Example Input-----
1
2
1 1
1 2
4 6
2 1
9 6
9 3
4 3

-----Example Output-----
2 2

-----Explanation-----
The original set of points are:

Upon adding the missing point $(2, 2)$, $N = 2$ rectangles can be formed:

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