vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Ms.Kox enjoys her job, but she does not like to waste extra time traveling to and from her office. After working for many years, she knows the shortest-distance route to her office on a regular day.

Recently, the city began regular maintenance of various roads. Every day a road gets blocked and no one can use it that day, but all other roads can be used. You are Ms. Kox's new intern and she needs some help. Every day, you need to determine the minimum distance that she has to travel to reach her office.

Input Format

There are N cities numbered 0 to N-1 and M bidirectional roads.  

The first line of the input contains two integers N and M.  
M lines follow, each containing three space-separated integers u , v and w, where u and v are cities connected by a bi-directional road and w is the length of this road. There is at most one road between any two cities and no road connects a city to itself.  
The next line contains two integers S and D. S is the city where Ms. Kox lives and D is the city where her office is located.  
The next line contains an integer Q, the number of queries.  
Q lines follow, each containing two integers u and v, where the road between u and v has been blocked that day.

Constraints

$0<N<200,000$ 

$0<M<200,000$ 

$0<Q<200,000$ 

$0<w<1001$ 

$0\leq S,D<N$

Output Format

Output Q lines, with each line containing the minimum distance Ms.Kox has to travel on that day. If there is no path, print "Infinity".

Sample Input
6 9  
0 1 1  
1 2 1  
2 3 1  
3 4 1  
4 5 1  
2 4 5  
3 5 8  
1 3 3  
0 2 4  
0 5  
9  
0 1  
1 2  
2 3  
3 4  
4 5  
2 4  
3 5  
1 3  
0 2

Sample Output
7  
6  
6  
8  
11  
5  
5  
5  
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have $n$ students under your control and you have to compose exactly two teams consisting of some subset of your students. Each student had his own skill, the $i$-th student skill is denoted by an integer $a_i$ (different students can have the same skills).

So, about the teams. Firstly, these two teams should have the same size. Two more constraints:  The first team should consist of students with distinct skills (i.e. all skills in the first team are unique).  The second team should consist of students with the same skills (i.e. all skills in the second team are equal). 

Note that it is permissible that some student of the first team has the same skill as a student of the second team.

Consider some examples (skills are given):  $[1, 2, 3]$, $[4, 4]$ is not a good pair of teams because sizes should be the same;  $[1, 1, 2]$, $[3, 3, 3]$ is not a good pair of teams because the first team should not contain students with the same skills;  $[1, 2, 3]$, $[3, 4, 4]$ is not a good pair of teams because the second team should contain students with the same skills;  $[1, 2, 3]$, $[3, 3, 3]$ is a good pair of teams;  $[5]$, $[6]$ is a good pair of teams. 

Your task is to find the maximum possible size $x$ for which it is possible to compose a valid pair of teams, where each team size is $x$ (skills in the first team needed to be unique, skills in the second team should be the same between them). A student cannot be part of more than one team.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of students. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the skill of the $i$-th student. Different students can have the same skills.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer — the maximum possible size $x$ for which it is possible to compose a valid pair of teams, where each team size is $x$.


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

Output
3
1
0
2



-----Note-----

In the first test case of the example, it is possible to construct two teams of size $3$: the first team is $[1, 2, 4]$ and the second team is $[4, 4, 4]$. Note, that there are some other ways to construct two valid teams of size $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string s of length n consisting of lowercase Latin letters. You may apply some operations to this string: in one operation you can delete some contiguous substring of this string, if all letters in the substring you delete are equal. For example, after deleting substring bbbb from string abbbbaccdd we get the string aaccdd.

Calculate the minimum number of operations to delete the whole string s.

Input

The first line contains one integer n (1 ≤ n ≤ 500) — the length of string s.

The second line contains the string s (|s| = n) consisting of lowercase Latin letters.

Output

Output a single integer — the minimal number of operation to delete string s.

Examples

Input


5
abaca


Output


3

Input


8
abcddcba


Output


4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Vasya got interested in finding extra-terrestrial intelligence. He made a simple extra-terrestrial signals’ receiver and was keeping a record of the signals for n days in a row. Each of those n days Vasya wrote a 1 in his notebook if he had received a signal that day and a 0 if he hadn’t. Vasya thinks that he has found extra-terrestrial intelligence if there is a system in the way the signals has been received, i.e. if all the intervals between successive signals are equal. Otherwise, Vasya thinks that the signals were sent by some stupid aliens no one cares about. Help Vasya to deduce from the information given by the receiver if he has found extra-terrestrial intelligence or not.

Input

The first line contains integer n (3 ≤ n ≤ 100) — amount of days during which Vasya checked if there were any signals. The second line contains n characters 1 or 0 — the record Vasya kept each of those n days. It’s guaranteed that the given record sequence contains at least three 1s.

Output

If Vasya has found extra-terrestrial intelligence, output YES, otherwise output NO.

Examples

Input

8
00111000


Output

YES


Input

7
1001011


Output

NO


Input

7
1010100


Output

YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string s and should process m queries. Each query is described by two 1-based indices l_{i}, r_{i} and integer k_{i}. It means that you should cyclically shift the substring s[l_{i}... r_{i}] k_{i} times. The queries should be processed one after another in the order they are given.

One operation of a cyclic shift (rotation) is equivalent to moving the last character to the position of the first character and shifting all other characters one position to the right.

For example, if the string s is abacaba and the query is l_1 = 3, r_1 = 6, k_1 = 1 then the answer is abbacaa. If after that we would process the query l_2 = 1, r_2 = 4, k_2 = 2 then we would get the string baabcaa.


-----Input-----

The first line of the input contains the string s (1 ≤ |s| ≤ 10 000) in its initial state, where |s| stands for the length of s. It contains only lowercase English letters.

Second line contains a single integer m (1 ≤ m ≤ 300) — the number of queries.

The i-th of the next m lines contains three integers l_{i}, r_{i} and k_{i} (1 ≤ l_{i} ≤ r_{i} ≤ |s|, 1 ≤ k_{i} ≤ 1 000 000) — the description of the i-th query.


-----Output-----

Print the resulting string s after processing all m queries.


-----Examples-----
Input
abacaba
2
3 6 1
1 4 2

Output
baabcaa



-----Note-----

The sample is described in problem statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string, The task is to count the number of alphabets present in the string.
Example 1:
Input:
S = "adjfjh23"
Output: 6
Explanation: only last 2 are not 
alphabets.
Example 2:
Input:
S = "n0ji#k$"
Output: 4
Explanation: #, $, 0 are not alphabets.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function Count() which takes the string S as inputs and returns alphabets count.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{5}
S contains only upper and lower case alphabets, digits and '#', '!', '$', '&' only.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:


Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Having solved the match issue, Mirko faced another challenging problem. His mom ordered him to read an article about the newest couples on the Croatian show-biz scene in the “Moja Tajna” magazine. The article is written in a very small font size which Mirko cannot read. Luckily, Mirko has a scanner in the closet which will enlarge the article for him.

The article is a matrix of characters with $R$ rows and $C$ columns. The characters are letters of the English alphabet, digits and the character ‘.’ (period). Mirko’s scanner supports two parameters, $Z_ R$ and $Z_ C$. It substitutes each character it scans with a matrix of $Z_ R$ rows and $Z_ C$ columns, where all entries are equal to the scanned character.

Mirko realized his scanner’s software no longer works so he needs your help.

-----Input-----
The first row contains four integers, $R$, $C$, $Z_ R$ and $Z_ C$. $R$ and $C$ are between $1$ and $50$, while $Z_ R$ and $Z_ C$ are between $1$ and $5$.

Each of the following $R$ rows contains $C$ characters each, representing the article from “Moja Tajna”.

-----Output-----
The output should be a matrix of characters with $R \cdot Z_ R$ rows and $C \cdot Z_ C$ columns, the enlarged article.

-----Examples-----
Sample Input:
3 3 1 2
.x.
x.x
.x.
Sample Output:
..xx..
xx..xx
..xx..

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Agneta and Beata are visiting the famous Swedish Amusement Park of Infinite Fun and Games. Their favourite attraction is the Infinitely Long Slides. Each slide can be viewed as an infinitely long, completely vertical spiral of radius $1$.

When projected into the (flat) ground, the first slide has $(0, 0)$ as its centre point, and the second one has $(1, 0)$ as its centre point. Furthermore, the start of the slides are at $(1, 0)$ and $(2, 0)$ respectively, and then proceeds counter-clockwise around their respective centres. When Agneta rides her slide (the first one), she does so with vertical speed $1\text { m/s}$, while Beatas slide has a bit higher gradient, so she goes with vertical speed $2\text { m/s}$. However, their angular speeds around the centre is both equal to $1 \text { rad/s}$. Since Beata is a little afraid of the slides, she always waits for Agneta to go first. $W$ seconds after Agneta went, Beata starts her descent.

To make the infinite ride a bit more fun, the amusement park gives a prize if the two riders on the slides manage to pass a ball between them at some point. This prize consists of a lot of chocolate, which is Beata’s favourite treat. To maximize their chances of passing the ball successfully, they want to wait until their Euclidean distance is the smallest possible during the ride. How small will this distance be?

-----Input-----
The first and only line of the input contains the decimal number $0 \le W \le 1000$. The number contains at most $6$ digits after the decimal point.

-----Output-----
Output a single number – the minimal Euclidean distance between Agneta and Beata during their trip. Your answer will be accepted if it is within a relative or absolute error of $10^{-4}$ of the judges’ answer.

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

Sample Input 2:
6.283185
Sample Output 2:
1

Sample Input 3:
42
Sample Output 3:
1.5228490019

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vanya is managed to enter his favourite site Codehorses. Vanya uses n distinct passwords for sites at all, however he can't remember which one exactly he specified during Codehorses registration.

Vanya will enter passwords in order of non-decreasing their lengths, and he will enter passwords of same length in arbitrary order. Just when Vanya will have entered the correct password, he is immediately authorized on the site. Vanya will not enter any password twice.

Entering any passwords takes one second for Vanya. But if Vanya will enter wrong password k times, then he is able to make the next try only 5 seconds after that. Vanya makes each try immediately, that is, at each moment when Vanya is able to enter password, he is doing that.

Determine how many seconds will Vanya need to enter Codehorses in the best case for him (if he spends minimum possible number of second) and in the worst case (if he spends maximum possible amount of seconds).


-----Input-----

The first line of the input contains two integers n and k (1 ≤ n, k ≤ 100) — the number of Vanya's passwords and the number of failed tries, after which the access to the site is blocked for 5 seconds.

The next n lines contains passwords, one per line — pairwise distinct non-empty strings consisting of latin letters and digits. Each password length does not exceed 100 characters.

The last line of the input contains the Vanya's Codehorses password. It is guaranteed that the Vanya's Codehorses password is equal to some of his n passwords.


-----Output-----

Print two integers — time (in seconds), Vanya needs to be authorized to Codehorses in the best case for him and in the worst case respectively.


-----Examples-----
Input
5 2
cba
abc
bb1
abC
ABC
abc

Output
1 15

Input
4 100
11
22
1
2
22

Output
3 4



-----Note-----

Consider the first sample case. As soon as all passwords have the same length, Vanya can enter the right password at the first try as well as at the last try. If he enters it at the first try, he spends exactly 1 second. Thus in the best case the answer is 1. If, at the other hand, he enters it at the last try, he enters another 4 passwords before. He spends 2 seconds to enter first 2 passwords, then he waits 5 seconds as soon as he made 2 wrong tries. Then he spends 2 more seconds to enter 2 wrong passwords, again waits 5 seconds and, finally, enters the correct password spending 1 more second. In summary in the worst case he is able to be authorized in 15 seconds.

Consider the second sample case. There is no way of entering passwords and get the access to the site blocked. As soon as the required password has length of 2, Vanya enters all passwords of length 1 anyway, spending 2 seconds for that. Then, in the best case, he immediately enters the correct password and the answer for the best case is 3, but in the worst case he enters wrong password of length 2 and only then the right one, spending 4 seconds at all.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a sequence $A = a_0, a_1, ..., a_{n-1}$. You are given the following information and questions.

* relate$(x, y, z)$: $a_y$ is greater than $a_x$ by $z$
* diff$(x, y)$: report the difference between $a_x$ and $a_y$ $(a_y - a_x)$

Constraints

* $2 \leq n \leq 100,000$
* $1 \leq q \leq 200,000$
* $0 \leq x, y < n$
* $x \ne y$
* $0 \leq z \leq 10000$
* There are no inconsistency in the given information

Input


$n \; q$
$query_1$
$query_2$
:
$query_q$


In the first line, $n$ and $q$ are given. Then, $q$ information/questions are given in the following format.


0 $x \; y\; z$


or


1 $x \; y$


where '0' of the first digit denotes the relate information and '1' denotes the diff question.

Output

For each diff question, print the difference between $a_x$ and $a_y$ $(a_y - a_x)$.

Example

Input

5 6
0 0 2 5
0 1 2 3
1 0 1
1 1 3
0 1 4 8
1 0 4


Output

2
?
10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lunar rover finally reached planet X. After landing, he met an obstacle, that contains permutation p of length n. Scientists found out, that to overcome an obstacle, the robot should make p an identity permutation (make p_i = i for all i).

Unfortunately, scientists can't control the robot. Thus the only way to make p an identity permutation is applying the following operation to p multiple times: 

  * Select two indices i and j (i ≠ j), such that p_j = i and swap the values of p_i and p_j. It takes robot (j - i)^2 seconds to do this operation. 

Positions i and j are selected by the robot (scientists can't control it). He will apply this operation while p isn't an identity permutation. We can show that the robot will make no more than n operations regardless of the choice of i and j on each operation.

Scientists asked you to find out the maximum possible time it will take the robot to finish making p an identity permutation (i. e. worst-case scenario), so they can decide whether they should construct a new lunar rover or just rest and wait. They won't believe you without proof, so you should build an example of p and robot's operations that maximizes the answer.

For a better understanding of the statement, read the sample description.

Input

The first line of input contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases.

Each of next t lines contains the single integer n (2 ≤ n ≤ 10^5) – the length of p.

Note, that p is not given to you. You should find the maximum possible time over all permutations of length n.

It is guaranteed, that the total sum of n over all test cases doesn't exceed 10^5.

Output

For each test case in the first line, print how many seconds will the robot spend in the worst case.

In the next line, print the initial value of p that you used to construct an answer.

In the next line, print the number of operations m ≤ n that the robot makes in your example.

In the each of next m lines print two integers i and j — indices of positions that the robot will swap on this operation. Note that p_j = i must holds (at the time of operation).

Example

Input


3
2
3
3


Output


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

Note

For n = 2, p can be either [1, 2] or [2, 1]. In the first case p is already identity, otherwise robot will make it an identity permutation in 1 second regardless of choise i and j on the first operation.

For n = 3, p can be equals [2, 3, 1].

  * If robot will select i = 3, j = 2 on the first operation, p will become [2, 1, 3] in one second. Now robot can select only i = 1, j = 2 or i = 2, j = 1. In both cases, p will become identity in one more second (2 seconds in total).
  * If robot will select i = 1, j = 3 on the first operation, p will become [1, 3, 2] in four seconds. Regardless of choise of i and j on the second operation, p will become identity in five seconds. 



We can show, that for permutation of length 3 robot will always finish all operation in no more than 5 seconds.

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 ≤ |s| ≤ 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.
There are n employees in Alternative Cake Manufacturing (ACM). They are now voting on some very important question and the leading world media are trying to predict the outcome of the vote.

Each of the employees belongs to one of two fractions: depublicans or remocrats, and these two fractions have opposite opinions on what should be the outcome of the vote. The voting procedure is rather complicated:   Each of n employees makes a statement. They make statements one by one starting from employees 1 and finishing with employee n. If at the moment when it's time for the i-th employee to make a statement he no longer has the right to vote, he just skips his turn (and no longer takes part in this voting).  When employee makes a statement, he can do nothing or declare that one of the other employees no longer has a right to vote. It's allowed to deny from voting people who already made the statement or people who are only waiting to do so. If someone is denied from voting he no longer participates in the voting till the very end.  When all employees are done with their statements, the procedure repeats: again, each employees starting from 1 and finishing with n who are still eligible to vote make their statements.  The process repeats until there is only one employee eligible to vote remaining and he determines the outcome of the whole voting. Of course, he votes for the decision suitable for his fraction. 

You know the order employees are going to vote and that they behave optimal (and they also know the order and who belongs to which fraction). Predict the outcome of the vote.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of employees. 

The next line contains n characters. The i-th character is 'D' if the i-th employee is from depublicans fraction or 'R' if he is from remocrats.


-----Output-----

Print 'D' if the outcome of the vote will be suitable for depublicans and 'R' if remocrats will win.


-----Examples-----
Input
5
DDRRR

Output
D

Input
6
DDRRRR

Output
R



-----Note-----

Consider one of the voting scenarios for the first sample:   Employee 1 denies employee 5 to vote.  Employee 2 denies employee 3 to vote.  Employee 3 has no right to vote and skips his turn (he was denied by employee 2).  Employee 4 denies employee 2 to vote.  Employee 5 has no right to vote and skips his turn (he was denied by employee 1).  Employee 1 denies employee 4.  Only employee 1 now has the right to vote so the voting ends with the victory of depublicans.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The objective of this Kata is to write a function that creates a dictionary of factors for a range of numbers.

The key for each list in the dictionary should be the number. The list associated with each key should possess the factors for the number.

If a number possesses no factors (only 1 and the number itself), the list for the key should be `['None']`

The function possesses two arguments (`n` and `m`). Where `n` is the starting number and `m` is the ending number.

For example: All factors for 2 (`n`) through to 6 (`m`) with the number being the key in the dictionary:

```python
{2: ['None'], 3: ['None'], 4: [2], 5: ['None'], 6: [2, 3]}
```

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