vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Increase and Decrease

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarpus has an array, consisting of *n* integers *a*1,<=*a*2,<=...,<=*a**n*. Polycarpus likes it when numbers in an array match. That's why he wants the array to have as many equal numbers as possible. For that Polycarpus performs the following operation multiple times:
 -  he chooses two elements of the array *a**i*, *a**j* (*i*<=≠<=*j*); -  he simultaneously increases number *a**i* by 1 and decreases number *a**j* by 1, that is, executes *a**i*<==<=*a**i*<=+<=1 and *a**j*<==<=*a**j*<=-<=1. 
The given operation changes exactly two distinct array elements. Polycarpus can apply the described operation an infinite number of times. 

Now he wants to know what maximum number of equal array elements he can get if he performs an arbitrary number of such operation. Help Polycarpus.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105) — the array size. The second line contains space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (|*a**i*|<=≤<=104) — the original array.

Output Specification:
Print a single integer — the maximum number of equal array elements he can get if he performs an arbitrary number of the given operation.

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

Demo Output:
['1\n', '3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a graph with N vertices and M edges, and there are two people on the graph: Takahashi and Aoki.
The i-th edge connects Vertex U_i and Vertex V_i.
The time it takes to traverse this edge is D_i minutes, regardless of direction and who traverses the edge (Takahashi or Aoki).
Takahashi departs Vertex S and Aoki departs Vertex T at the same time. Takahashi travels to Vertex T and Aoki travels to Vertex S, both in the shortest time possible.
Find the number of the pairs of ways for Takahashi and Aoki to choose their shortest paths such that they never meet (at a vertex or on an edge) during the travel, modulo 10^9 + 7.

-----Constraints-----
 - 1 \leq N \leq 100 000
 - 1 \leq M \leq 200 000
 - 1 \leq S, T \leq N
 - S \neq T
 - 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
 - 1 \leq D_i \leq 10^9 (1 \leq i \leq M)
 - If i \neq j, then (U_i, V_i) \neq (U_j, V_j) and (U_i, V_i) \neq (V_j, U_j).
 - U_i \neq V_i (1 \leq i \leq M)
 - D_i are integers.
 - The given graph is connected.

-----Input-----
Input is given from Standard Input in the following format:
N M
S T
U_1 V_1 D_1
U_2 V_2 D_2
:
U_M V_M D_M

-----Output-----
Print the answer.

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

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

There are two ways to choose shortest paths that satisfies the condition:
 - Takahashi chooses the path 1 \rightarrow 2 \rightarrow 3, and Aoki chooses the path 3 \rightarrow 4 \rightarrow 1.
 - Takahashi chooses the path 1 \rightarrow 4 \rightarrow 3, and Aoki chooses the path 3 \rightarrow 2 \rightarrow 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of $n$ positive integers $a_1, a_2, \ldots, a_n$. Your task is to calculate the number of arrays of $n$ positive integers $b_1, b_2, \ldots, b_n$ such that:

$1 \le b_i \le a_i$ for every $i$ ($1 \le i \le n$), and

$b_i \neq b_{i+1}$ for every $i$ ($1 \le i \le n - 1$).

The number of such arrays can be very large, so print it modulo $998\,244\,353$.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the array $a$.

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


-----Output-----

Print the answer modulo $998\,244\,353$ in a single line.


-----Examples-----

Input
3
2 2 2
Output
2
Input
2
2 3
Output
4
Input
3
1 1 1
Output
0


-----Note-----

In the first test case possible arrays are $[1, 2, 1]$ and $[2, 1, 2]$.

In the second test case possible arrays are $[1, 2]$, $[1, 3]$, $[2, 1]$ and $[2, 3]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
All techniques in the ninja world consist of hand seals. At the moment Naruto is learning a new technique, which consists of $n\cdot m$ different seals, denoted by distinct numbers. All of them were written in an $n\times m$ table.

The table is lost now. Naruto managed to remember elements of each row from left to right, and elements of each column from top to bottom, but he doesn't remember the order of rows and columns. Please restore the table consistent with this data so that Naruto will be able to learn the new technique.


-----Input-----

The first line of the input contains the only integer $t$ ($1\leq t\leq 100\,000$) denoting the number of test cases. Their descriptions follow.

The first line of each test case description consists of two space-separated integers $n$ and $m$ ($1 \leq n, m \leq 500$) standing for the number of rows and columns in the table, respectively. All hand seals are encoded by the positive integers from $1$ to $n\cdot m$.

The following $n$ lines contain $m$ space separated integers each, denoting elements of an arbitrary row in the table left to right.

The following $m$ lines contain $n$ space separated integers each, denoting elements of an arbitrary column in the table top to bottom.

Sum of $nm$ over all test cases does not exceed $250\,000$. It is guaranteed that each row occurs in the input exactly once, as well as each column. It is also guaranteed that each number from $1$ to $nm$ occurs exactly once in all rows, as well as in all columns. Finally, it is guaranteed that a table consistent with the input exists.


-----Output-----

For each test case, output $n$ lines with $m$ space-separated integers each, denoting the restored table. One can show that the answer is always unique.


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

Output
1 2 3 
6 5 4 
3 
1 
2 



-----Note-----

Consider the first test case. The matrix is $2 \times 3$. You are given the rows and columns in arbitrary order.

One of the rows is $[6, 5, 4]$. One of the rows is $[1, 2, 3]$.

One of the columns is $[1, 6]$. One of the columns is $[2, 5]$. One of the columns is $[3, 4]$.

You are to reconstruct the matrix. The answer is given in the output.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Once Bob needed to find the second order statistics of a sequence of integer numbers. Lets choose each number from the sequence exactly once and sort them. The value on the second position is the second order statistics of the given sequence. In other words it is the smallest element strictly greater than the minimum. Help Bob solve this problem.

Input Specification:
The first input line contains integer *n* (1<=≤<=*n*<=≤<=100) — amount of numbers in the sequence. The second line contains *n* space-separated integer numbers — elements of the sequence. These numbers don't exceed 100 in absolute value.

Output Specification:
If the given sequence has the second order statistics, output this order statistics, otherwise output NO.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n points on the plane. You need to delete exactly k of them (k < n) so that the diameter of the set of the remaining n - k points were as small as possible. The diameter of a set of points is the maximum pairwise distance between the points of the set. The diameter of a one point set equals zero.

Input

The first input line contains a pair of integers n, k (2 ≤ n ≤ 1000, 1 ≤ k ≤ 30, k < n) — the numbers of points on the plane and the number of points to delete, correspondingly.

Next n lines describe the points, one per line. Each description consists of a pair of integers xi, yi (0 ≤ xi, yi ≤ 32000) — the coordinates of the i-th point. The given points can coincide.

Output

Print k different space-separated integers from 1 to n — the numbers of points to delete. The points are numbered in the order, in which they are given in the input from 1 to n. You can print the numbers in any order. If there are multiple solutions, print any of them.

Examples

Input

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


Output

5 2

Input

4 1
0 0
0 0
1 1
1 1


Output

3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
As the guys fried the radio station facilities, the school principal gave them tasks as a punishment. Dustin's task was to add comments to nginx configuration for school's website. The school has *n* servers. Each server has a name and an ip (names aren't necessarily unique, but ips are). Dustin knows the ip and name of each server. For simplicity, we'll assume that an nginx command is of form "command ip;" where command is a string consisting of English lowercase letter only, and ip is the ip of one of school servers.

Each ip is of form "a.b.c.d" where *a*, *b*, *c* and *d* are non-negative integers less than or equal to 255 (with no leading zeros). The nginx configuration file Dustin has to add comments to has *m* commands. Nobody ever memorizes the ips of servers, so to understand the configuration better, Dustin has to comment the name of server that the ip belongs to at the end of each line (after each command). More formally, if a line is "command ip;" Dustin has to replace it with "command ip; #name" where name is the name of the server with ip equal to ip.

Dustin doesn't know anything about nginx, so he panicked again and his friends asked you to do his task for him.

Input Specification:
The first line of input contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=1000).

The next *n* lines contain the names and ips of the servers. Each line contains a string name, name of the server and a string ip, ip of the server, separated by space (1<=≤<=|*name*|<=≤<=10, *name* only consists of English lowercase letters). It is guaranteed that all ip are distinct.

The next *m* lines contain the commands in the configuration file. Each line is of form "command ip;" (1<=≤<=|*command*|<=≤<=10, command only consists of English lowercase letters). It is guaranteed that ip belongs to one of the *n* school servers.

Output Specification:
Print *m* lines, the commands in the configuration file after Dustin did his task.

Demo Input:
['2 2\nmain 192.168.0.2\nreplica 192.168.0.1\nblock 192.168.0.1;\nproxy 192.168.0.2;\n', '3 5\ngoogle 8.8.8.8\ncodeforces 212.193.33.27\nserver 138.197.64.57\nredirect 138.197.64.57;\nblock 8.8.8.8;\ncf 212.193.33.27;\nunblock 8.8.8.8;\ncheck 138.197.64.57;\n']

Demo Output:
['block 192.168.0.1; #replica\nproxy 192.168.0.2; #main\n', 'redirect 138.197.64.57; #server\nblock 8.8.8.8; #google\ncf 212.193.33.27; #codeforces\nunblock 8.8.8.8; #google\ncheck 138.197.64.57; #server\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Quark Codejam's number QC(n, m) represents the number of ways to partition a set of n things into m nonempty subsets. For example, there are seven ways to split a four-element set into two parts:

{1, 2, 3} ∪ {4}, {1, 2, 4} ∪ {3}, {1, 3, 4} ∪ {2}, {2, 3, 4} ∪ {1},

{1, 2} ∪ {3, 4}, {1, 3} ∪ {2, 4}, {1, 4} ∪ {2, 3}.

We can compute QC(n, m) using the recurrence,

QC(n, m) = mQC(n − 1, m) + QC(n − 1, m − 1), for integers 1 < m < n.

but your task is a somewhat different: given integers n and m, compute the parity of QC(n, m), i.e. QC(n, m) mod 2.

Example : 

QC(4, 2) mod 2 = 1. 
Write a program that reads two positive integers n and m, computes QC(n, m) mod 2, and writes the

result.

-----Input-----
The input begins with a single positive integer on a line by itself indicating the number of the cases. This line is followed by the input cases.

The input consists two integers n and m separated by a space, with 1 ≤ m ≤ n ≤ 1000000000.

-----Output-----
For each test case, print the output.

The output should be the integer S(n, m) mod 2.
Sample Input
1

4 2
Sample Output
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A crop circle suddenly appeared on the vast agricultural land of Argentina. A total of n crop circles were confirmed, including overlapping, popping, large, and small ones.

When a mystery hunter tried to capture the whole picture of a crop circle from the air, he found it difficult to show the beautiful pattern in the image because the outline of each circle was not clear.

Therefore, the mystery hunter proposed to emphasize the contour by installing a string of special material along the contour.

The part where the string is installed is the part on the circumference of one crop circle that is not included in any other crop circle.

The film crew asked you to create a program to measure the required string length. Enter the center coordinates and radius of each crop circle and create a program to report the length of the string to be installed.

For reference, the first and second cases of the input / output examples are shown in FIGS. 1 and 2, respectively. The part of the string is shown by a thick line.


<image>


Figure 1



<image>


Figure 2



Constraints

* n ≤ 100
* -1000 ≤ xi, yi ≤ 1000
* 0 <ri ≤ 100

Input

Multiple datasets are given as input. Each dataset is given in the following format:

n (number of crop circles: integer)
x1 y1 r1 (center coordinates and radius of the first circle: real numbers separated by blanks)
x2 y2 r2 (center coordinates and radius of the second circle: real numbers separated by blanks)
..
..
xn yn rn (center coordinates and radius of the nth circle: real numbers separated by blanks)


When n is 0, it indicates the end of input.

Output

Output the string length on one line for each dataset. The output may contain an error of 0.000001 or less.

Example

Input

4
6 4 2
4 7 3
7 10 3
13 6 1
4
7 4 2
4 7 3
7 10 3
11 6 3
0


Output

39.664699289572
45.627024663706

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An accordion is a string (yes, in the real world accordions are musical instruments, but let's forget about it for a while) which can be represented as a concatenation of: an opening bracket (ASCII code $091$), a colon (ASCII code $058$), some (possibly zero) vertical line characters (ASCII code $124$), another colon, and a closing bracket (ASCII code $093$). The length of the accordion is the number of characters in it.

For example, [::], [:||:] and [:|||:] are accordions having length $4$, $6$ and $7$. (:|:), {:||:}, [:], ]:||:[ are not accordions. 

You are given a string $s$. You want to transform it into an accordion by removing some (possibly zero) characters from it. Note that you may not insert new characters or reorder existing ones. Is it possible to obtain an accordion by removing characters from $s$, and if so, what is the maximum possible length of the result?


-----Input-----

The only line contains one string $s$ ($1 \le |s| \le 500000$). It consists of lowercase Latin letters and characters [, ], : and |.


-----Output-----

If it is not possible to obtain an accordion by removing some characters from $s$, print $-1$. Otherwise print maximum possible length of the resulting accordion.


-----Examples-----
Input
|[a:b:|]

Output
4

Input
|]:[|:]

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day Vasya the Hipster decided to count how many socks he had. It turned out that he had a red socks and b blue socks.

According to the latest fashion, hipsters should wear the socks of different colors: a red one on the left foot, a blue one on the right foot.

Every day Vasya puts on new socks in the morning and throws them away before going to bed as he doesn't want to wash them.

Vasya wonders, what is the maximum number of days when he can dress fashionable and wear different socks, and after that, for how many days he can then wear the same socks until he either runs out of socks or cannot make a single pair from the socks he's got.

Can you help him?


-----Input-----

The single line of the input contains two positive integers a and b (1 ≤ a, b ≤ 100) — the number of red and blue socks that Vasya's got.


-----Output-----

Print two space-separated integers — the maximum number of days when Vasya can wear different socks and the number of days when he can wear the same socks until he either runs out of socks or cannot make a single pair from the socks he's got.

Keep in mind that at the end of the day Vasya throws away the socks that he's been wearing on that day.


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

Output
1 1

Input
2 3

Output
2 0

Input
7 3

Output
3 2



-----Note-----

In the first sample Vasya can first put on one pair of different socks, after that he has two red socks left to wear on the second day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a binary string S consists only of 0s and 1s. The task is to calculate the number of substrings that have more 1s than 0s.
Example 1:
Input:
S = "011"
Output: 4
Explanation: There are 4 substring which 
has more 1s than 0s. i.e "011","1","11" and "1"
Example 2:
Input:
S = "0000"
Output: 0
Explanation: There is no substring
which has more 1s than 0s
Your Task:  
You dont need to read input or print anything. Complete the function countSubstring() which takes the string S as input parameter and returns the number of substring which has more 1s than 0s.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
Constraints:
1 < |S| < 10^{5}
|S| denotes the length of the string S

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string s consisting only of first 20 lowercase Latin letters ('a', 'b', ..., 't').

Recall that the substring s[l; r] of the string s is the string s_l s_{l + 1} ... s_r. For example, the substrings of "codeforces" are "code", "force", "f", "for", but not "coder" and "top".

You can perform the following operation no more than once: choose some substring s[l; r] and reverse it (i.e. the string s_l s_{l + 1} ... s_r becomes s_r s_{r - 1} ... s_l).

Your goal is to maximize the length of the maximum substring of s consisting of distinct (i.e. unique) characters.

The string consists of distinct characters if no character in this string appears more than once. For example, strings "abcde", "arctg" and "minecraft" consist of distinct characters but strings "codeforces", "abacaba" do not consist of distinct characters.

Input

The only line of the input contains one string s consisting of no more than 10^6 characters 'a', 'b', ..., 't' (first 20 lowercase Latin letters).

Output

Print one integer — the maximum possible length of the maximum substring of s consisting of distinct characters after reversing no more than one its substring.

Examples

Input


abacaba


Output


3


Input


abcdecdf


Output


6


Input


aabbcc


Output


3


Input


abcdeefc


Output


6

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

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
There are several days left before the fiftieth birthday of a famous Berland's writer Berlbury. In this connection the local library decided to make an exposition of the works of this famous science-fiction writer. It was decided as well that it is necessary to include into the exposition only those books that were published during a particular time period. It is obvious that if the books differ much in size, the visitors will not like it. That was why the organizers came to the opinion, that the difference between the highest and the lowest books in the exposition should be not more than *k* millimeters.

The library has *n* volumes of books by Berlbury, arranged in chronological order of their appearance. The height of each book in millimeters is know, it is *h**i*. As Berlbury is highly respected in the city, the organizers want to include into the exposition as many books as possible, and to find out what periods of his creative work they will manage to cover. You are asked to help the organizers cope with this hard task.

Input Specification:
The first line of the input data contains two integer numbers separated by a space *n* (1<=≤<=*n*<=≤<=105) and *k* (0<=≤<=*k*<=≤<=106) — the amount of books by Berlbury in the library, and the maximum allowed height difference between the lowest and the highest books. The second line contains *n* integer numbers separated by a space. Each number *h**i* (1<=≤<=*h**i*<=≤<=106) is the height of the *i*-th book in millimeters.

Output Specification:
In the first line of the output data print two numbers *a* and *b* (separate them by a space), where *a* is the maximum amount of books the organizers can include into the exposition, and *b* — the amount of the time periods, during which Berlbury published *a* books, and the height difference between the lowest and the highest among these books is not more than *k* milllimeters.

In each of the following *b* lines print two integer numbers separated by a space — indexes of the first and the last volumes from each of the required time periods of Berlbury's creative work.

Demo Input:
['3 3\n14 12 10\n', '2 0\n10 10\n', '4 5\n8 19 10 13\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let us define the oddness of a permutation p = {p_1,\ p_2,\ ...,\ p_n} of {1,\ 2,\ ...,\ n} as \sum_{i = 1}^n |i - p_i|.
Find the number of permutations of {1,\ 2,\ ...,\ n} of oddness k, modulo 10^9+7.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq n \leq 50
 - 0 \leq k \leq n^2

-----Input-----
Input is given from Standard Input in the following format:
n k

-----Output-----
Print the number of permutations of {1,\ 2,\ ...,\ n} of oddness k, modulo 10^9+7.

-----Sample Input-----
3 2

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

There are six permutations of {1,\ 2,\ 3}. Among them, two have oddness of 2:  {2,\ 1,\ 3} and {1,\ 3,\ 2}.

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