vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Consider a string of $n$ characters, $\boldsymbol{\mathrm{~S~}}$, of where each character is indexed from $\mbox{0}$ to $n-1$.

You are given $\textit{q}$ queries in the form of two integer indices: ${\mbox{left}}$ and $\textit{right}$. For each query, count and print the number of different substrings of $\boldsymbol{\mathrm{~S~}}$ in the inclusive range between ${\mbox{left}}$ and $\textit{right}$. 

Note: Two substrings are different if their sequence of characters differs by at least one. For example, given the string $\boldsymbol{s}=$ aab, substrings $\boldsymbol{s}_{[0,0]}=$ a and $\boldsymbol{s}_{[1,1]}\:=\:$ a are the same but substrings $\textbf{s}_{[0,1]}\:=\:$ aa and $\boldsymbol{s}_{[1,2]}=$ ab are different.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ and $\textit{q}$. 

The second line contains a single string denoting $\boldsymbol{\mathrm{~S~}}$. 

Each of the $\textit{q}$ subsequent lines contains two space-separated integers describing the respective values of ${\mbox{left}}$ and $\textit{right}$ for a query.

Constraints

$0\leq left\leq right\leq n-1$  
String $\boldsymbol{\mathrm{~S~}}$ consists of lowercase English alphabetic letters (i.e., a to z) only.

Subtasks  

For $30\%$ of the test cases, $1\leq n,q\leq100$  
For $50\%$ of the test cases, $1\leq n,q\leq3000$  
For $100\%$ of the test cases, $1\leq n,q\leq10^5$  

Output Format

For each query, print the number of different substrings in the inclusive range between index ${\mbox{left}}$ and index $\textit{right}$ on a new line. 

Sample Input 0
5 5
aabaa
1 1
1 4
1 1
1 4
0 2

Sample Output 0
1
8
1
8
5

Explanation 0

Given $\boldsymbol{s}=$ aabaa, we perform the following $q=5$ queries:

1 1: The only substring of a is itself, so we print $\mbox{1}$ on a new line.
1 4: The substrings of abaa are a, b, ab, ba, aa, aba, baa, and abaa, so we print $8$ on a new line.
1 1: The only substring of a is itself, so we print $\mbox{1}$ on a new line.
1 4: The substrings of abaa are a, b, ab, ba, aa, aba, baa, and abaa, so we print $8$ on a new line.
0 2: The substrings of aab are a, b, aa, ab, and aab, so we print $5$ on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a square array of integers A, we want the minimum sum of a falling path through A.
A falling path starts at any element in the first row, and chooses one element from each row.  The next row's choice must be in a column that is different from the previous row's column by at most one.
 
Example 1:
Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation: 
The possible falling paths are:


[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]

The falling path with the smallest sum is [1,4,7], so the answer is 12.
 
Constraints:

1 <= A.length == A[0].length <= 100
-100 <= A[i][j] <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Isaac H. Ives attended an international student party and made a lot of girl friends (as many other persons expected). To strike up a good friendship with them, he decided to have dates with them. However, it is hard for him to schedule dates because he made so many friends. Thus he decided to find the best schedule using a computer program. The most important criterion in scheduling is how many different girl friends he will date. Of course, the more friends he will date, the better the schedule is. However, though he has the ability to write a program finding the best schedule, he doesn’t have enough time to write it.

Your task is to write a program to find the best schedule instead of him.



Input

The input consists of a series of data sets. The first line of each data set contains a single positive integer N (N ≤ 1,000) that represents the number of persons Isaac made friends with in the party. The next line gives Isaac’s schedule, followed by N lines that give his new friends’ schedules. Each schedule consists of a positive integer M that represents the number of available days followed by M positive integers each of which represents an available day.

The input is terminated by a line that contains a single zero. This is not part of data sets and should not be processed.

Output

For each data set, print a line that contains the maximum number of girl friends Isaac can have dates with.

Example

Input

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


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Many years ago Berland was a small country where only $n$ people lived. Each person had some savings: the $i$-th one had $a_i$ burles.

The government considered a person as wealthy if he had at least $x$ burles. To increase the number of wealthy people Berland decided to carry out several reforms. Each reform looked like that:   the government chooses some subset of people (maybe all of them);  the government takes all savings from the chosen people and redistributes the savings among the chosen people equally. 

For example, consider the savings as list $[5, 1, 2, 1]$: if the government chose the $1$-st and the $3$-rd persons then it, at first, will take all $5 + 2 = 7$ burles and after that will return $3.5$ burles to the chosen people. As a result, the savings will become $[3.5, 1, 3.5, 1]$.

A lot of data was lost from that time, so we don't know how many reforms were implemented and to whom. All we can do is ask you to calculate the maximum possible number of wealthy people after several (maybe zero) reforms.


-----Input-----

The first line contains single integer $T$ ($1 \le T \le 1000$) — the number of test cases.

Next $2T$ lines contain the test cases — two lines per test case. The first line contains two integers $n$ and $x$ ($1 \le n \le 10^5$, $1 \le x \le 10^9$) — the number of people and the minimum amount of money to be considered as wealthy.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the initial savings of each person.

It's guaranteed that the total sum of $n$ doesn't exceed $10^5$.


-----Output-----

Print $T$ integers — one per test case. For each test case print the maximum possible number of wealthy people after several (maybe zero) reforms.


-----Example-----
Input
4
4 3
5 1 2 1
4 10
11 9 11 9
2 5
4 3
3 7
9 4 9

Output
2
4
0
3



-----Note-----

The first test case is described in the statement.

In the second test case, the government, for example, could carry out two reforms: $[\underline{11}, \underline{9}, 11, 9] \rightarrow [10, 10, \underline{11}, \underline{9}] \rightarrow [10, 10, 10, 10]$.

In the third test case, the government couldn't make even one person wealthy.

In the fourth test case, the government could choose all people to carry out a reform: $[\underline{9}, \underline{4}, \underline{9}] \rightarrow [7\frac{1}{3}, 7\frac{1}{3}, 7\frac{1}{3}]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a given array $a$ consisting of $n$ integers and a given integer $m$ find if it is possible to reorder elements of the array $a$ in such a way that $\sum_{i=1}^{n}{\sum_{j=i}^{n}{\frac{a_j}{j}}}$ equals $m$? It is forbidden to delete elements as well as insert new elements. Please note that no rounding occurs during division, for example, $\frac{5}{2}=2.5$.


-----Input-----

The first line contains a single integer $t$ — the number of test cases ($1 \le t \le 100$). The test cases follow, each in two lines.

The first line of a test case contains two integers $n$ and $m$ ($1 \le n \le 100$, $0 \le m \le 10^6$). The second line contains integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^6$) — the elements of the array.


-----Output-----

For each test case print "YES", if it is possible to reorder the elements of the array in such a way that the given formula gives the given value, and "NO" otherwise.


-----Example-----
Input
2
3 8
2 5 1
4 4
0 1 2 3

Output
YES
NO



-----Note-----

In the first test case one of the reorders could be $[1, 2, 5]$. The sum is equal to $(\frac{1}{1} + \frac{2}{2} + \frac{5}{3}) + (\frac{2}{2} + \frac{5}{3}) + (\frac{5}{3}) = 8$. The brackets denote the inner sum $\sum_{j=i}^{n}{\frac{a_j}{j}}$, while the summation of brackets corresponds to the sum over $i$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
At $3147.3$ meters high, Fansipan is the tallest mountain in the Indochina peninsula. To promote tourism, $n$ stations were built on the mountain, numbered from $1$ to $n$.

Two companies, Mobi and Vina are in charge of operating cable cars connecting the stations. Each of the two companies have $k$ cable cars. The $i$-th cable car of Mobi connects two stations $MS_ i$ and $ME_ i$. The $i$-th cable car of Vina connects two stations $VS_ i$ and $VE_ i$.

Two stations are called connected by a company, iff we can go from one station to the other by using cable cars only of that company. To achieve peaceful cooperation, the two companies agreed with the following conditions:
 - For every valid $i$, $MS_ i < ME_ i$ and $VS_ i < VE_ i$.
 - All $MS_ i$ are unique, all $ME_ i$ are unique.
 - All $VS_ i$ are unique, all $VE_ i$ are unique.
 - For any $i \ne j$, if $MS_ i < MS_ j$, then $ME_ i < ME_ j$.
 - For any $i \ne j$, if $VS_ i < VS_ j$, then $VE_ i < VE_ j$.
 - No pair of stations is connected by both companies. In other words, for every pair of stations $i$ and $j$, if $i$ and $j$ are connected by Mobi, they should not be connected by Vina, and vice versa.

Given $n$ and $k$, your task is to check whether it is possible for Mobi and Vina to each operates $k$ cable cars, satisfying all the above conditions.

-----Input-----
The input contains two integers $n$ and $k$, separated by a single space $(1 \le k < n \le 100)$.

-----Output-----
For each test case, if it is not possible to satisfy all the conditions, print ‘NO’. Otherwise, print ‘YES’, followed by $2 \cdot k$ lines. In the first $k$ lines, the $i$-th line contains two integers $MS_ i$ and $ME_ i$. In the last $k$ lines, the $i$-th line contains two integers $VS_ i$ and $VE_ i$.

-----Examples-----
Sample Input:
3 1
Sample Output:
YES
1 2
1 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Little Elephant loves permutations of integers from 1 to n very much. But most of all he loves sorting them. To sort a permutation, the Little Elephant repeatedly swaps some elements. As a result, he must receive a permutation 1, 2, 3, ..., n.

This time the Little Elephant has permutation p1, p2, ..., pn. Its sorting program needs to make exactly m moves, during the i-th move it swaps elements that are at that moment located at the ai-th and the bi-th positions. But the Little Elephant's sorting program happened to break down and now on every step it can equiprobably either do nothing or swap the required elements.

Now the Little Elephant doesn't even hope that the program will sort the permutation, but he still wonders: if he runs the program and gets some permutation, how much will the result of sorting resemble the sorted one? For that help the Little Elephant find the mathematical expectation of the number of permutation inversions after all moves of the program are completed.

We'll call a pair of integers i, j (1 ≤ i < j ≤ n) an inversion in permutatuon p1, p2, ..., pn, if the following inequality holds: pi > pj.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 1000, n > 1) — the permutation size and the number of moves. The second line contains n distinct integers, not exceeding n — the initial permutation. Next m lines each contain two integers: the i-th line contains integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the positions of elements that were changed during the i-th move.

Output

In the only line print a single real number — the answer to the problem. The answer will be considered correct if its relative or absolute error does not exceed 10 - 6.

Examples

Input

2 1
1 2
1 2


Output

0.500000000


Input

4 3
1 3 2 4
1 2
2 3
1 4


Output

3.000000000

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A film festival is coming up in the city N. The festival will last for exactly *n* days and each day will have a premiere of exactly one film. Each film has a genre — an integer from 1 to *k*.

On the *i*-th day the festival will show a movie of genre *a**i*. We know that a movie of each of *k* genres occurs in the festival programme at least once. In other words, each integer from 1 to *k* occurs in the sequence *a*1,<=*a*2,<=...,<=*a**n* at least once.

Valentine is a movie critic. He wants to watch some movies of the festival and then describe his impressions on his site.

As any creative person, Valentine is very susceptive. After he watched the movie of a certain genre, Valentine forms the mood he preserves until he watches the next movie. If the genre of the next movie is the same, it does not change Valentine's mood. If the genres are different, Valentine's mood changes according to the new genre and Valentine has a stress.

Valentine can't watch all *n* movies, so he decided to exclude from his to-watch list movies of one of the genres. In other words, Valentine is going to choose exactly one of the *k* genres and will skip all the movies of this genre. He is sure to visit other movies.

Valentine wants to choose such genre *x* (1<=≤<=*x*<=≤<=*k*), that the total number of after-movie stresses (after all movies of genre *x* are excluded) were minimum.

Input Specification:
The first line of the input contains two integers *n* and *k* (2<=≤<=*k*<=≤<=*n*<=≤<=105), where *n* is the number of movies and *k* is the number of genres.

The second line of the input contains a sequence of *n* positive integers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=*k*), where *a**i* is the genre of the *i*-th movie. It is guaranteed that each number from 1 to *k* occurs at least once in this sequence.

Output Specification:
Print a single number — the number of the genre (from 1 to *k*) of the excluded films. If there are multiple answers, print the genre with the minimum number.

Demo Input:
['10 3\n1 1 2 3 2 3 3 1 1 3\n', '7 3\n3 1 3 2 3 1 2\n']

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

Note:
In the first sample if we exclude the movies of the 1st genre, the genres 2, 3, 2, 3, 3, 3 remain, that is 3 stresses; if we exclude the movies of the 2nd genre, the genres 1, 1, 3, 3, 3, 1, 1, 3 remain, that is 3 stresses; if we exclude the movies of the 3rd genre the genres 1, 1, 2, 2, 1, 1 remain, that is 2 stresses.

In the second sample whatever genre Valentine excludes, he will have exactly 3 stresses.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Teachers of one programming summer school decided to make a surprise for the students by giving them names in the style of the "Hobbit" movie. Each student must get a pseudonym maximally similar to his own name. The pseudonym must be a name of some character of the popular saga and now the teachers are busy matching pseudonyms to student names.

There are n students in a summer school. Teachers chose exactly n pseudonyms for them. Each student must get exactly one pseudonym corresponding to him. Let us determine the relevance of a pseudonym b to a student with name a as the length of the largest common prefix a and b. We will represent such value as <image>. Then we can determine the quality of matching of the pseudonyms to students as a sum of relevances of all pseudonyms to the corresponding students.

Find the matching between students and pseudonyms with the maximum quality.

Input

The first line contains number n (1 ≤ n ≤ 100 000) — the number of students in the summer school.

Next n lines contain the name of the students. Each name is a non-empty word consisting of lowercase English letters. Some names can be repeating.

The last n lines contain the given pseudonyms. Each pseudonym is a non-empty word consisting of small English letters. Some pseudonyms can be repeating.

The total length of all the names and pseudonyms doesn't exceed 800 000 characters.

Output

In the first line print the maximum possible quality of matching pseudonyms to students.

In the next n lines describe the optimal matching. Each line must have the form a b (1 ≤ a, b ≤ n), that means that the student who was number a in the input, must match to the pseudonym number b in the input.

The matching should be a one-to-one correspondence, that is, each student and each pseudonym should occur exactly once in your output. If there are several optimal answers, output any.

Examples

Input

5
gennady
galya
boris
bill
toshik
bilbo
torin
gendalf
smaug
galadriel


Output

11
4 1
2 5
1 3
5 2
3 4

Note

The first test from the statement the match looks as follows: 

  * bill  →  bilbo (lcp = 3) 
  * galya  →  galadriel (lcp = 3) 
  * gennady  →  gendalf (lcp = 3) 
  * toshik  →  torin (lcp = 2) 
  * boris  →  smaug (lcp = 0) 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this kata you're expected to sort an array of 32-bit integers in ascending order of the number of **on** bits they have.

E.g Given the array **[7, 6, 15, 8]**

- 7 has **3 on** bits  (000...0**111**)
- 6 has **2 on** bits  (000...00**11**)
- 15 has **4 on** bits (000...**1111**)
- 8 has **1 on** bit   (000...**1**000)

So the array in sorted order would be **[8, 6, 7, 15]**.

In cases where two numbers have the same number of bits, compare their real values instead.

E.g between 10 **(...1010)** and 12 **(...1100)**, they both have the same number of **on** bits '**2**' but the integer 10 is less than 12 so it comes first in sorted order.

Your task is to write the function `sortBybit()` that takes an array of integers and sort them as described above.

```if-not:haskell
Note: Your function should modify the input rather than creating a new array.
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a string S consisting of `0` and `1`. Find the number of strings, modulo 998244353, that can result from applying the following operation on S zero or more times:

* Remove the two characters at the beginning of S, erase one of them, and reinsert the other somewhere in S. This operation can be applied only when S has two or more characters.

Constraints

* 1 \leq |S| \leq 300
* S consists of `0` and `1`.

Input

Input is given from Standard Input in the following format:


S


Output

Print the number of strings, modulo 998244353, that can result from applying the operation on S zero or more times.

Examples

Input

0001


Output

8


Input

110001


Output

24


Input

11101111011111000000000110000001111100011111000000001111111110000000111111111


Output

697354558

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are two strings S and T consisting of lowercase English letters. Concatenate T and S in this order, without space in between, and print the resulting string.

-----Constraints-----
 - S and T are strings consisting of lowercase English letters.
 - The lengths of S and T are between 1 and 100 (inclusive).

-----Input-----
Input is given from Standard Input in the following format:
S T

-----Output-----
Print the resulting string.

-----Sample Input-----
oder atc

-----Sample Output-----
atcoder

When S =  oder and T =  atc, concatenating T and S in this order results in atcoder.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We know that lucky digits are digits 4 and 7, however Vasya's got another favorite digit 0 and he assumes it also is lucky! Lucky numbers are such non-negative integers whose decimal record only contains lucky digits. For example, numbers 0, 47, 7074 are lucky, but 1, 7377, 895,  -7 are not.

Vasya has t important positive integers he needs to remember. Vasya is quite superstitious and he wants to remember lucky numbers only, so he is asking you for each important number to represent it as a sum of exactly six lucky numbers (Vasya just can't remember more numbers). Then Vasya can just remember these six numbers and calculate the important number at any moment.

For each of t important integers represent it as the sum of six lucky numbers or state that this is impossible.

Input

The first line contains a single integer t (1 ≤ t ≤ 5000).

Next t lines contain a single positive integer ni (1 ≤ ni ≤ 1018) — the list of important numbers.

Please, do not use the %lld to read or write 64-bit integers С++. It is preferred to read the cin, cout streams or the %I64d specifier.

Output

Print t lines. The i-th line must contain the answer for the i-th important number: if the solution exists, the line must contain exactly six lucky numbers the sum of which equals ni, if the solution doesn't exist the string must contain a single integer -1.

If there are multiple answers print any of them.

Examples

Input

5
42
17
444
7
51


Output

7 7 7 7 7 7
-1
400 0 40 0 4 0
7 0 0 0 0 0
47 4 0 0 0 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let S(n) denote the sum of the digits in the decimal notation of n.
For example, S(101) = 1 + 0 + 1 = 2.
Given an integer N, determine if S(N) divides N.

-----Constraints-----
 - 1 \leq N \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N

-----Output-----
If S(N) divides N, print Yes; if it does not, print No.

-----Sample Input-----
12

-----Sample Output-----
Yes

In this input, N=12.
As S(12) = 1 + 2 = 3, S(N) divides N.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have to create a function,named `insertMissingLetters`, that takes in a `string` and outputs the same string processed in a particular way.

The function should insert **only after the first occurrence** of each character of the input string, all the **alphabet letters** that:

-**are NOT** in the original string  
-**come after** the letter of the string you are processing  

Each added letter should be in `uppercase`, the letters of the original string will always be in `lowercase`.


Example:  


`input`: "holly"  

`missing letters`: "a,b,c,d,e,f,g,i,j,k,m,n,p,q,r,s,t,u,v,w,x,z"  

`output`: "hIJKMNPQRSTUVWXZoPQRSTUVWXZlMNPQRSTUVWXZlyZ"  


You don't need to validate input, the input string will always contain a certain amount of lowercase letters  (min 1 / max 50).

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