vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Once little Vasya read an article in a magazine on how to make beautiful handmade garland from colored paper. Vasya immediately went to the store and bought n colored sheets of paper, the area of each sheet is 1 square meter.

The garland must consist of exactly m pieces of colored paper of arbitrary area, each piece should be of a certain color. To make the garland, Vasya can arbitrarily cut his existing colored sheets into pieces. Vasya is not obliged to use all the sheets to make the garland.

Vasya wants the garland to be as attractive as possible, so he wants to maximize the total area of ​​m pieces of paper in the garland. Calculate what the maximum total area of ​​the pieces of paper in the garland Vasya can get.


-----Input-----

The first line contains a non-empty sequence of n (1 ≤ n ≤ 1000) small English letters ("a"..."z"). Each letter means that Vasya has a sheet of paper of the corresponding color.

The second line contains a non-empty sequence of m (1 ≤ m ≤ 1000) small English letters that correspond to the colors of the pieces of paper in the garland that Vasya wants to make.


-----Output-----

Print an integer that is the maximum possible total area of the pieces of paper in the garland Vasya wants to get or -1, if it is impossible to make the garland from the sheets he's got. It is guaranteed that the answer is always an integer.


-----Examples-----
Input
aaabbac
aabbccac

Output
6

Input
a
z

Output
-1


-----Note-----

In the first test sample Vasya can make an garland of area 6: he can use both sheets of color b, three (but not four) sheets of color a and cut a single sheet of color c in three, for example, equal pieces. Vasya can use the resulting pieces to make a garland of area 6.

In the second test sample Vasya cannot make a garland at all — he doesn't have a sheet of color z.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
After waking up at *hh*:*mm*, Andrew realised that he had forgotten to feed his only cat for yet another time (guess why there's only one cat). The cat's current hunger level is *H* points, moreover each minute without food increases his hunger by *D* points.

At any time Andrew can visit the store where tasty buns are sold (you can assume that is doesn't take time to get to the store and back). One such bun costs *C* roubles and decreases hunger by *N* points. Since the demand for bakery drops heavily in the evening, there is a special 20% discount for buns starting from 20:00 (note that the cost might become rational). Of course, buns cannot be sold by parts.

Determine the minimum amount of money Andrew has to spend in order to feed his cat. The cat is considered fed if its hunger level is less than or equal to zero.

Input Specification:
The first line contains two integers *hh* and *mm* (00<=≤<=*hh*<=≤<=23,<=00<=≤<=*mm*<=≤<=59) — the time of Andrew's awakening.

The second line contains four integers *H*, *D*, *C* and *N* (1<=≤<=*H*<=≤<=105,<=1<=≤<=*D*,<=*C*,<=*N*<=≤<=102).

Output Specification:
Output the minimum amount of money to within three decimal digits. You answer is considered correct, if its absolute or relative error does not exceed 10<=-<=4.

Formally, let your answer be *a*, and the jury's answer be *b*. Your answer is considered correct if .

Demo Input:
['19 00\n255 1 100 1\n', '17 41\n1000 6 15 11\n']

Demo Output:
['25200.0000\n', '1365.0000\n']

Note:
In the first sample Andrew can visit the store at exactly 20:00. The cat's hunger will be equal to 315, hence it will be necessary to purchase 315 buns. The discount makes the final answer 25200 roubles.

In the second sample it's optimal to visit the store right after he wakes up. Then he'll have to buy 91 bins per 15 roubles each and spend a total of 1365 roubles.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A frog is currently at the point $0$ on a coordinate axis $Ox$. It jumps by the following algorithm: the first jump is $a$ units to the right, the second jump is $b$ units to the left, the third jump is $a$ units to the right, the fourth jump is $b$ units to the left, and so on.

Formally:   if the frog has jumped an even number of times (before the current jump), it jumps from its current position $x$ to position $x+a$;  otherwise it jumps from its current position $x$ to position $x-b$. 

Your task is to calculate the position of the frog after $k$ jumps.

But... One more thing. You are watching $t$ different frogs so you have to answer $t$ independent queries.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 1000$) — the number of queries.

Each of the next $t$ lines contain queries (one query per line).

The query is described as three space-separated integers $a, b, k$ ($1 \le a, b, k \le 10^9$) — the lengths of two types of jumps and the number of jumps, respectively.


-----Output-----

Print $t$ integers. The $i$-th integer should be the answer for the $i$-th query.


-----Example-----
Input
6
5 2 3
100 1 4
1 10 5
1000000000 1 6
1 1 1000000000
1 1 999999999

Output
8
198
-17
2999999997
0
1



-----Note-----

In the first query frog jumps $5$ to the right, $2$ to the left and $5$ to the right so the answer is $5 - 2 + 5 = 8$.

In the second query frog jumps $100$ to the right, $1$ to the left, $100$ to the right and $1$ to the left so the answer is $100 - 1 + 100 - 1 = 198$.

In the third query the answer is $1 - 10 + 1 - 10 + 1 = -17$.

In the fourth query the answer is $10^9 - 1 + 10^9 - 1 + 10^9 - 1 = 2999999997$.

In the fifth query all frog's jumps are neutralized by each other so the answer is $0$.

The sixth query is the same as the fifth but without the last jump so the answer is $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You like tracking airplane flights a lot. Specifically, you maintain history of an airplane’s flight at several instants and record them in your notebook. Today, you have recorded N such records h1, h2, ..., hN, denoting the heights of some airplane at several instants. These records mean that airplane was first flying on height h1, then started changing its height to h2, then from h2 to h3 and so on. The airplanes are usually on cruise control while descending or ascending, so 
you can assume that plane will smoothly increase/decrease its height from hi to hi + 1 with a constant speed. You can see that during this period, the airplane will cover all possible heights in the range [min(hi, hi+1), max(hi, hi+1)] (both inclusive). It is easy to see that the plane will be at all possible heights in the range exactly a single instant of time during this ascend/descend.

You are interested in finding the maximum integer K such that the plane was at some height exactly K times during the flight.

-----Input-----
There is a single test case.
First line of the input contains an integer N denoting the number of records of heights of the plane.
Second line contains N space separated integers denoting h1, h2, ..., hN.

-----Output-----
Output a single maximum integer K in one line, such that the plane was at some height exactly K times during the flight.

-----Constraints-----
- hi ≠ hi+1

-----Subtasks-----
Subtask #1: (30 points)
- 1 ≤ N ≤ 1000
- 1 ≤ hi ≤ 1000

Subtask #2: (70 points)
- 1 ≤ N ≤ 105
- 1 ≤ hi ≤ 109

-----Example-----
Input:
5
1 2 3 2 3

Output:
3

-----Explanation-----

The flight can be draw as:

3  /\/
2 /
1

There are infinitely many heights at which the plane was 3 times during the flight, for example 2.5, 2.1. Notice that the plane was only 2 times at height 2. Moreover, there are no height at which the plane was more than 3 times, so the answer is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two pirates Polycarpus and Vasily play a very interesting game. They have n chests with coins, the chests are numbered with integers from 1 to n. Chest number i has a_{i} coins. 

Polycarpus and Vasily move in turns. Polycarpus moves first. During a move a player is allowed to choose a positive integer x (2·x + 1 ≤ n) and take a coin from each chest with numbers x, 2·x, 2·x + 1. It may turn out that some chest has no coins, in this case the player doesn't take a coin from this chest. The game finishes when all chests get emptied.

Polycarpus isn't a greedy scrooge. Polycarpys is a lazy slob. So he wonders in what minimum number of moves the game can finish. Help Polycarpus, determine the minimum number of moves in which the game can finish. Note that Polycarpus counts not only his moves, he also counts Vasily's moves.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of chests with coins. The second line contains a sequence of space-separated integers: a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1000), where a_{i} is the number of coins in the chest number i at the beginning of the game.


-----Output-----

Print a single integer — the minimum number of moves needed to finish the game. If no sequence of turns leads to finishing the game, print -1.


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

Output
-1

Input
3
1 2 3

Output
3



-----Note-----

In the first test case there isn't a single move that can be made. That's why the players won't be able to empty the chests.

In the second sample there is only one possible move x = 1. This move should be repeated at least 3 times to empty the third chest.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a positive integer N.
We will choose an integer K between 2 and N (inclusive), then we will repeat the operation below until N becomes less than K.
 - Operation: if K divides N, replace N with N/K; otherwise, replace N with N-K.
In how many choices of K will N become 1 in the end?

-----Constraints-----
 - 2 \leq N \leq 10^{12}
 - N is an integer.

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

-----Output-----
Print the number of choices of K in which N becomes 1 in the end.

-----Sample Input-----
6

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

There are three choices of K in which N becomes 1 in the end: 2, 5, and 6.
In each of these choices, N will change as follows:
 - When K=2: 6 \to 3 \to 1
 - When K=5: 6 \to 1
 - When K=6: 6 \to 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ashish has two strings a and b, each of length n, and an integer k. The strings only contain lowercase English letters.

He wants to convert string a into string b by performing some (possibly zero) operations on a.

In one move, he can either 

  * choose an index i (1 ≤ i≤ n-1) and swap a_i and a_{i+1}, or 
  * choose an index i (1 ≤ i ≤ n-k+1) and if a_i, a_{i+1}, …, a_{i+k-1} are all equal to some character c (c ≠ 'z'), replace each one with the next character (c+1), that is, 'a' is replaced by 'b', 'b' is replaced by 'c' and so on. 



Note that he can perform any number of operations, and the operations can only be performed on string a. 

Help Ashish determine if it is possible to convert string a into b after performing some (possibly zero) operations on it.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^5) — the number of test cases. The description of each test case is as follows.

The first line of each test case contains two integers n (2 ≤ n ≤ 10^6) and k (1 ≤ k ≤ n).

The second line of each test case contains the string a of length n consisting of lowercase English letters.

The third line of each test case contains the string b of length n consisting of lowercase English letters.

It is guaranteed that the sum of values n among all test cases does not exceed 10^6.

Output

For each test case, print "Yes" if Ashish can convert a into b after some moves, else print "No".

You may print the letters of the answer in any case (upper or lower).

Example

Input


4
3 3
abc
bcd
4 2
abba
azza
2 1
zz
aa
6 2
aaabba
ddddcc


Output


No
Yes
No
Yes

Note

In the first test case it can be shown that it is impossible to convert a into b.

In the second test case,

"abba" \xrightarrow{inc} "acca" \xrightarrow{inc} … \xrightarrow{inc} "azza".

Here "swap" denotes an operation of the first type, and "inc" denotes an operation of the second type.

In the fourth test case,

"aaabba" \xrightarrow{swap} "aaabab" \xrightarrow{swap} "aaaabb" \xrightarrow{inc} … \xrightarrow{inc} "ddaabb" \xrightarrow{inc} … \xrightarrow{inc} "ddddbb" \xrightarrow{inc} … \xrightarrow{inc} "ddddcc".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The XOR pair representation (XPR) of a positive integer $N$ is defined as a pair of integers $(A, B)$ such that:
- $1 \le A \le B \le N$
- $A \oplus B = N$
- if there is no way to choose $A$ and $B$ satisfying the above conditions, $A = B = -1$
- otherwise, the value of $A$ should be the smallest possible
These conditions uniquely define the XPR. Next, we define a function $F(N)$ = the value of $B$ in $XPR(N)$, and a function $G(L, R) = \sum\limits_{i=L}^R F(i)$.
You are given $L$ and $R$. Compute $G(L, R)$.

-----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 and only line of each test case contains two space-separated integers $L$ and $R$.

-----Output-----
For each test case, print a single line containing one integer — the value of the function $G(L, R)$.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le L \le R \le 10^9$

-----Example Input-----
5
1 10
3 6
4 10
10 17
100 159

-----Example Output-----
28
9
28
79
7485

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little town Nsk consists of *n* junctions connected by *m* bidirectional roads. Each road connects two distinct junctions and no two roads connect the same pair of junctions. It is possible to get from any junction to any other junction by these roads. The distance between two junctions is equal to the minimum possible number of roads on a path between them.

In order to improve the transportation system, the city council asks mayor to build one new road. The problem is that the mayor has just bought a wonderful new car and he really enjoys a ride from his home, located near junction *s* to work located near junction *t*. Thus, he wants to build a new road in such a way that the distance between these two junctions won't decrease. 

You are assigned a task to compute the number of pairs of junctions that are not connected by the road, such that if the new road between these two junctions is built the distance between *s* and *t* won't decrease.

Input Specification:
The firt line of the input contains integers *n*, *m*, *s* and *t* (2<=≤<=*n*<=≤<=1000, 1<=≤<=*m*<=≤<=1000, 1<=≤<=*s*,<=*t*<=≤<=*n*, *s*<=≠<=*t*) — the number of junctions and the number of roads in Nsk, as well as the indices of junctions where mayors home and work are located respectively. The *i*-th of the following *m* lines contains two integers *u**i* and *v**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*, *u**i*<=≠<=*v**i*), meaning that this road connects junctions *u**i* and *v**i* directly. It is guaranteed that there is a path between any two junctions and no two roads connect the same pair of junctions.

Output Specification:
Print one integer — the number of pairs of junctions not connected by a direct road, such that building a road between these two junctions won't decrease the distance between junctions *s* and *t*.

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

Demo Output:
['0\n', '5\n', '3\n']

Note:
none

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

Consider an arithmetic expression built by combining single-digit positive integers with addition symbols `+`, multiplication symbols `*`, and parentheses `(` `)`, defined by the following grammar rules with the start symbol `E`.


E ::= T | E '+' T
T ::= F | T '*' F
F ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '(' E ')'


When such an arithmetic expression is viewed as a string, its substring, that is, a contiguous sequence of characters within the string, may again form an arithmetic expression. Given an integer n and a string s representing an arithmetic expression, let us count the number of its substrings that can be read as arithmetic expressions with values computed equal to n.

Input

The input consists of multiple datasets, each in the following format.

> n
>  s
>

A dataset consists of two lines. In the first line, the target value n is given. n is an integer satisfying 1 ≤ n ≤ 109. The string s given in the second line is an arithmetic expression conforming to the grammar defined above. The length of s does not exceed 2×106. The nesting depth of the parentheses in the string is at most 1000.

The end of the input is indicated by a line containing a single zero. The sum of the lengths of s in all the datasets does not exceed 5×106.

Output

For each dataset, output in one line the number of substrings of s that conform to the above grammar and have the value n. The same sequence of characters appearing at different positions should be counted separately.

Sample Input


3
(1+2)*3+3
2
1*1*1+1*1*1
587
1*(2*3*4)+5+((6+7*8))*(9)
0


Output for the Sample Input


4
9
2






Example

Input

3
(1+2)*3+3
2
1*1*1+1*1*1
587
1*(2*3*4)+5+((6+7*8))*(9)
0


Output

4
9
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We will play a one-player game using a number line and N pieces.
First, we place each of these pieces at some integer coordinate.
Here, multiple pieces can be placed at the same coordinate.
Our objective is to visit all of the M coordinates X_1, X_2, ..., X_M with these pieces, by repeating the following move:
Move: Choose a piece and let x be its coordinate. Put that piece at coordinate x+1 or x-1.
Note that the coordinates where we initially place the pieces are already regarded as visited.
Find the minimum number of moves required to achieve the objective.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 10^5
 - 1 \leq M \leq 10^5
 - -10^5 \leq X_i \leq 10^5
 - X_1, X_2, ..., X_M are all different.

-----Input-----
Input is given from Standard Input in the following format:
N M
X_1 X_2 ... X_M

-----Output-----
Find the minimum number of moves required to achieve the objective.

-----Sample Input-----
2 5
10 12 1 2 14

-----Sample Output-----
5

The objective can be achieved in five moves as follows, and this is the minimum number of moves required.
 - Initially, put the two pieces at coordinates 1 and 10.
 - Move the piece at coordinate 1 to 2.
 - Move the piece at coordinate 10 to 11.
 - Move the piece at coordinate 11 to 12.
 - Move the piece at coordinate 12 to 13.
 - Move the piece at coordinate 13 to 14.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Please notice the unusual memory limit of this problem.

Orac likes games. Recently he came up with the new game, "Game of Life".

You should play this game on a black and white grid with $n$ rows and $m$ columns. Each cell is either black or white.

For each iteration of the game (the initial iteration is $0$), the color of each cell will change under the following rules: If there are no adjacent cells with the same color as this cell on the current iteration, the color of it on the next iteration will be the same. Otherwise, the color of the cell on the next iteration will be different.

Two cells are adjacent if they have a mutual edge.

Now Orac has set an initial situation, and he wants to know for the cell $(i,j)$ (in $i$-th row and $j$-th column), what will be its color at the iteration $p$. He may ask you these questions several times. 


-----Input-----

The first line contains three integers $n,m,t\ (1\le n,m\le 1000, 1\le t\le 100\,000)$, representing the number of rows, columns, and the number of Orac queries.

Each of the following $n$ lines contains a binary string of length $m$, the $j$-th character in $i$-th line represents the initial color of cell $(i,j)$. '0' stands for white, '1' stands for black.

Each of the following $t$ lines contains three integers $i,j,p\ (1\le i\le n, 1\le j\le m, 1\le p\le 10^{18})$, representing a query from Orac.


-----Output-----

Print $t$ lines, in $i$-th line you should print the answer to the $i$-th query by Orac. If the color of this cell is black, you should print '1'; otherwise, you should write '0'.


-----Examples-----
Input
3 3 3
000
111
000
1 1 1
2 2 2
3 3 3

Output
1
1
1

Input
5 2 2
01
10
01
10
01
1 1 4
5 1 4

Output
0
0

Input
5 5 3
01011
10110
01101
11010
10101
1 1 4
1 2 3
5 5 3

Output
1
0
1

Input
1 1 3
0
1 1 1
1 1 2
1 1 3

Output
0
0
0



-----Note----- [Image] 

For the first example, the picture above shows the initial situation and the color of cells at the iteration $1$, $2$, and $3$. We can see that the color of $(1,1)$ at the iteration $1$ is black, the color of $(2,2)$ at the iteration $2$ is black, and the color of $(3,3)$ at the iteration $3$ is also black.

For the second example, you can prove that the cells will never change their colors.

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