vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The CS & IT Department students have been facing tough competitions from each other since ages, in being the best in research & innovation.
This time CS Department is taken the edge over IT Department by designing a special weather predictor device which inputs previous years data and perform analysis over it to give a prediction of current weather condition.
This device needs a unique string code to be unlocked and activated, which is always kept safe with the Head Of Department's Computer.
But this time IT Dept. students are able to hack the code over the network and they have distorted the original code by removing some characters and by replacing some characters.
The CS Department has to rebuild the code in order to make their device work.
You are given the actual code and the distorted code, you have to find the minimum number of operations to be performed to rebuild the distorted code.
An operation can be 

(1) Adding one or more character(s)

(2) Replacing one character with another.

Adding one or more character does not consume time whereas replacing a single character require one unit of time.

You have to find out the minimum unit of time in which CS Dept. can rebuild the distorted code.

Input :

First line of the input contains an integer T denoting the number of test cases.
T test cases follow where each test case contains two lines containing two strings, first line contains the distorted string D, and the next line contains the actual string S.

Output :

Print the minimum unit of time required to rebuild the distorted string.

Constraints :
1 ≤ T ≤ 50
1 ≤ Length Of D ≤ Length Of S ≤ 5000

SAMPLE INPUT
2
porrisa
poornimainst
waatdes
weather

SAMPLE OUTPUT
3
3

Explanation

Test Case #1:
We can change three characters in "porrisa" to create "oornima" and then "p" can be appended at the start and "inst" at the last.
So only Three Replacement operations are required.

Similarly for Test Case #2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
All bus tickets in Berland have their numbers. A number consists of n digits (n is even). Only k decimal digits d_1, d_2, ..., d_k can be used to form ticket numbers. If 0 is among these digits, then numbers may have leading zeroes. For example, if n = 4 and only digits 0 and 4 can be used, then 0000, 4004, 4440 are valid ticket numbers, and 0002, 00, 44443 are not.

A ticket is lucky if the sum of first n / 2 digits is equal to the sum of remaining n / 2 digits. 

Calculate the number of different lucky tickets in Berland. Since the answer may be big, print it modulo 998244353.

Input

The first line contains two integers n and k (2 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ k ≤ 10) — the number of digits in each ticket number, and the number of different decimal digits that may be used. n is even.

The second line contains a sequence of pairwise distinct integers d_1, d_2, ..., d_k (0 ≤ d_i ≤ 9) — the digits that may be used in ticket numbers. The digits are given in arbitrary order.

Output

Print the number of lucky ticket numbers, taken modulo 998244353.

Examples

Input

4 2
1 8


Output

6


Input

20 1
6


Output

1


Input

10 5
6 1 4 0 3


Output

569725


Input

1000 7
5 4 0 1 8 3 2


Output

460571165

Note

In the first example there are 6 lucky ticket numbers: 1111, 1818, 1881, 8118, 8181 and 8888.

There is only one ticket number in the second example, it consists of 20 digits 6. This ticket number is lucky, so the answer is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hongcow's teacher heard that Hongcow had learned about the cyclic shift, and decided to set the following problem for him.

You are given a list of n strings s1, s2, ..., sn contained in the list A.

A list X of strings is called stable if the following condition holds.

First, a message is defined as a concatenation of some elements of the list X. You can use an arbitrary element as many times as you want, and you may concatenate these elements in any arbitrary order. Let SX denote the set of of all messages you can construct from the list. Of course, this set has infinite size if your list is nonempty.

Call a single message good if the following conditions hold: 

  * Suppose the message is the concatenation of k strings w1, w2, ..., wk, where each wi is an element of X. 
  * Consider the |w1| + |w2| + ... + |wk| cyclic shifts of the string. Let m be the number of these cyclic shifts of the string that are elements of SX. 
  * A message is good if and only if m is exactly equal to k. 



The list X is called stable if and only if every element of SX is good.

Let f(L) be 1 if L is a stable list, and 0 otherwise.

Find the sum of f(L) where L is a nonempty contiguous sublist of A (there are <image> contiguous sublists in total).

Input

The first line of input will contain a single integer n (1 ≤ n ≤ 30), denoting the number of strings in the list.

The next n lines will each contain a string si (<image>).

Output

Print a single integer, the number of nonempty contiguous sublists that are stable.

Examples

Input

4
a
ab
b
bba


Output

7


Input

5
hh
ee
ll
ll
oo


Output

0


Input

6
aab
ab
bba
b
ab
c


Output

13

Note

For the first sample, there are 10 sublists to consider. Sublists ["a", "ab", "b"], ["ab", "b", "bba"], and ["a", "ab", "b", "bba"] are not stable. The other seven sublists are stable.

For example, X = ["a", "ab", "b"] is not stable, since the message "ab" + "ab" = "abab" has four cyclic shifts ["abab", "baba", "abab", "baba"], which are all elements of SX.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are two sequences a=\{a_0,\ldots,a_{N-1}\} and b=\{b_0,\ldots,b_{N-1}\} of N non-negative integers each.
Snuke will choose an integer k such that 0 \leq k < N and an integer x not less than 0, to make a new sequence of length N, a'=\{a_0',\ldots,a_{N-1}'\}, as follows:
 - a_i'= a_{i+k \mod N}\ XOR \ x
Find all pairs (k,x) such that a' will be equal to b.What is \mbox{ XOR }?

The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:

 - When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.
For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)


-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - 0 \leq a_i,b_i < 2^{30}
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
a_0 a_1 ... a_{N-1}
b_0 b_1 ... b_{N-1}

-----Output-----
Print all pairs (k, x) such that a' and b will be equal, using one line for each pair, in ascending order of k (ascending order of x for pairs with the same k).
If there are no such pairs, the output should be empty.

-----Sample Input-----
3
0 2 1
1 2 3

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

If (k,x)=(1,3),
 - a_0'=(a_1\ XOR \ 3)=1
 - a_1'=(a_2\ XOR \ 3)=2
 - a_2'=(a_0\ XOR \ 3)=3
and we have a' = b.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recall that string $a$ is a subsequence of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly zero or all) characters. For example, for the string $a$="wowwo", the following strings are subsequences: "wowwo", "wowo", "oo", "wow", "", and others, but the following are not subsequences: "owoo", "owwwo", "ooo".

The wow factor of a string is the number of its subsequences equal to the word "wow". Bob wants to write a string that has a large wow factor. However, the "w" key on his keyboard is broken, so he types two "v"s instead. 

Little did he realise that he may have introduced more "w"s than he thought. Consider for instance the string "ww". Bob would type it as "vvvv", but this string actually contains three occurrences of "w":   "vvvv"  "vvvv"  "vvvv" 

For example, the wow factor of the word "vvvovvv" equals to four because there are four wows:  "vvvovvv"  "vvvovvv"  "vvvovvv"  "vvvovvv" 

Note that the subsequence "vvvovvv" does not count towards the wow factor, as the "v"s have to be consecutive.

For a given string $s$, compute and output its wow factor. Note that it is not guaranteed that it is possible to get $s$ from another string replacing "w" with "vv". For example, $s$ can be equal to "vov".


-----Input-----

The input contains a single non-empty string $s$, consisting only of characters "v" and "o". The length of $s$ is at most $10^6$.


-----Output-----

Output a single integer, the wow factor of $s$.


-----Examples-----
Input
vvvovvv

Output
4

Input
vvovooovovvovoovoovvvvovovvvov

Output
100



-----Note-----

The first example is explained in the legend.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kulyash stays in room that has a single bulb and N buttons. The bulb is initially on.

The initial states of the buttons are stored in a binary string S of length N — if S_{i} is 0, the i-th button is off, and if S_{i} is 1, the i-th button is on. If Kulyash toggles any single button then the state of the bulb reverses i.e. the bulb lights up if it was off and vice versa. 

Kulyash has toggled some buttons and the final states of the buttons are stored in another binary string R of length N. He asks you to determine the final state of the bulb.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of three lines of input.
- The first line of each test case contains an integer N — the number of buttons.
- The second line of each test case contains a binary string S — the initial states of the buttons.
- The third line of each test case contains a binary string R — the final states of the buttons.

------ Output Format ------ 

For each test case, output on a new line the final state of the bulb (0 for off and 1 for on).

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$
$S$ and $R$ are binary strings, i.e, contain only the characters $0$ and $1$.

----- Sample Input 1 ------ 
2
3
000
001
2
00
11

----- Sample Output 1 ------ 
0
1

----- explanation 1 ------ 
Test case $1$: All the buttons are initially off and finally the state of only one button has changed so the state of the bulb reverses once i.e. it turns off.

Test case $2$: All the buttons are initially off and finally the states of two buttons have changed so the state of the bulb reverses twice i.e. it remains on.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two strings $S$ and $R$. Each of these strings has length $N$. We want to make $S$ equal to $R$ by performing the following operation some number of times (possibly zero):
- Choose two integers $a$ and $b$ such that $1 \le a \le b \le N$.
- For each $i$ such that $a \le i \le b$, replace the $i$-th character of $S$ by the $i$-th character of $R$.
Suppose that we make $S$ equal to $R$ by performing this operation $k$ times, in such a way that the total number of replaced characters (i.e. the sum of all $k$ values of $b-a+1$) is $l$. Then, the cost of this process is defined as $k \cdot l$.
Find the minimum cost with which we can make $S$ equal to $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 line of each test case contains a single string $S$.
- The second line contains a single string $R$.

-----Output-----
For each test case, print a single line containing one integer ― the minimum cost.

-----Constraints-----
- $1 \le T \le 4,000$
- $1 \le N \le 10^6$
- $|S| = |R| = N$
- $S$ and $R$ contain only lowercase English letters
- the sum of $N$ over all test cases does not exceed $2 \cdot 10^6$

-----Example Input-----
1
adefb
bdefa

-----Example Output-----
4

-----Explanation-----
Example case 1: $S$ can be made equal to $R$ in two moves. First, we replace $S_1$ by $R_1$ and then replace $S_5$ by $R_5$. We have $k = l = 2$, so the cost is $2 \cdot 2 = 4$. If we wanted to perform only one operation, the cost would be $5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One Big Software Company has n employees numbered from 1 to n. The director is assigned number 1. Every employee of the company except the director has exactly one immediate superior. The director, of course, doesn't have a superior.

We will call person a a subordinates of another person b, if either b is an immediate supervisor of a, or the immediate supervisor of a is a subordinate to person b. In particular, subordinates of the head are all other employees of the company.

To solve achieve an Important Goal we need to form a workgroup. Every person has some efficiency, expressed by a positive integer a_{i}, where i is the person's number. The efficiency of the workgroup is defined as the total efficiency of all the people included in it.

The employees of the big software company are obsessed with modern ways of work process organization. Today pair programming is at the peak of popularity, so the workgroup should be formed with the following condition. Each person entering the workgroup should be able to sort all of his subordinates who are also in the workgroup into pairs. In other words, for each of the members of the workgroup the number of his subordinates within the workgroup should be even.

Your task is to determine the maximum possible efficiency of the workgroup formed at observing the given condition. Any person including the director of company can enter the workgroup.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 2·10^5) — the number of workers of the Big Software Company. 

Then n lines follow, describing the company employees. The i-th line contains two integers p_{i}, a_{i} (1 ≤ a_{i} ≤ 10^5) — the number of the person who is the i-th employee's immediate superior and i-th employee's efficiency. For the director p_1 =  - 1, for all other people the condition 1 ≤ p_{i} < i is fulfilled.


-----Output-----

Print a single integer — the maximum possible efficiency of the workgroup.


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

Output
17



-----Note-----

In the sample test the most effective way is to make a workgroup from employees number 1, 2, 4, 5, 6.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
While swimming at the beach, Mike has accidentally dropped his cellphone into the water. There was no worry as he bought a cheap replacement phone with an old-fashioned keyboard. The keyboard has only ten digital equal-sized keys, located in the following way:

Together with his old phone, he lost all his contacts and now he can only remember the way his fingers moved when he put some number in. One can formally consider finger movements as a sequence of vectors connecting centers of keys pressed consecutively to put in a number. For example, the finger movements for number "586" are the same as finger movements for number "253":

Mike has already put in a number by his "finger memory" and started calling it, so he is now worrying, can he be sure that he is calling the correct number? In other words, is there any other number, that has the same finger movements?

Input Specification:
The first line of the input contains the only integer *n* (1<=≤<=*n*<=≤<=9) — the number of digits in the phone number that Mike put in.

The second line contains the string consisting of *n* digits (characters from '0' to '9') representing the number that Mike put in.

Output Specification:
If there is no other phone number with the same finger movements and Mike can be sure he is calling the correct number, print "YES" (without quotes) in the only line.

Otherwise print "NO" (without quotes) in the first line.

Demo Input:
['3\n586\n', '2\n09\n', '9\n123456789\n', '3\n911\n']

Demo Output:
['NO\n', 'NO\n', 'YES\n', 'YES\n']

Note:
You can find the picture clarifying the first sample case in the statement above.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a linear function f(x) = Ax + B. Let's define g^{(0)}(x) = x and g^{(}n)(x) = f(g^{(}n - 1)(x)) for n > 0. For the given integer values A, B, n and x find the value of g^{(}n)(x) modulo 10^9 + 7.


-----Input-----

The only line contains four integers A, B, n and x (1 ≤ A, B, x ≤ 10^9, 1 ≤ n ≤ 10^18) — the parameters from the problem statement.

Note that the given value n can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.


-----Output-----

Print the only integer s — the value g^{(}n)(x) modulo 10^9 + 7.


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

Output
7

Input
3 4 2 1

Output
25

Input
3 4 3 1

Output
79

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has a rectangular piece of paper. He puts it on a big board in such a way that two sides of the paper are horizontal and two are vertical, and then he performs a sequence of $N$ operations. You are given a string $S$ with length $N$; for each valid $i$, the $i$-th character of $S$ determines the type of the $i$-th operation:
- 'R': Pick up the paper from the right side and fold it onto the left side.
- 'L': Pick up the paper from the left side and fold it onto the right side.
- 'U': Pick up the paper from the upper side and fold it onto the bottom side.
- 'D': Pick up the paper from the bottom side and fold it onto the upper side.
The paper is folded in such a way that there is still a flat rectangular sheet of paper lying on the table after each operation, but it consists of multiple layers of the original sheet. The lengths of the horizontal and vertical sides of the resulting sheet (after performing these $N$ operations) are $W$ and $H$ respectively. Let's build an Euclidean coordinate system on the paper, where the point $(0, 0)$ corresponds to the bottom left corner and $(W, H)$ to the upper right corner.
Chef then draws $M$ points on this folded sheet of paper. The ink used to draw them soaks deep into the paper, so each point is drawn on all layers of the paper (and also on both faces of each layer). 
Finally, Chef completely unfolds the paper. He's asking you to compute the distance between the nearest pair of points.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains four space-separated integers $N$, $M$, $W$ and $H$.
- The second line contains a single string $S$.
- Each of the following $M$ lines contains two space-separated integers $X$ and $Y$ denoting the coordinates of one point.

-----Output-----
For each test case, print a single line containing one real number ― the minimum distance. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

-----Constraints-----
- $1 \le T \le 50$
- $2 \le M \le 1,000$
- $1 \le N \le 1,000$
- $3 \le W, H \le 10^9$
- $1 \le X \le W-1$
- $1 \le Y \le H-1$
- the points are pairwise distinct

-----Subtasks-----
Subtask #1 (50 points): all characters of $S$ are 'U'
Subtask #2 (50 points): original constraints

-----Example Input-----
2
6 2 10 10
ULRDDL
4 4
5 5
4 2 10 10
RUDL
1 1
9 9

-----Example Output-----
1.41421356237
2.00000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A function f is defined as follows F(N)= (1) +(2*3) + (4*5*6) ... N. Given an integer N the task is to print the F(N)th term.
Example 1:
Input: N = 5
Output: 365527
Explaination: F(5) = 1 + 2*3 + 4*5*6 + 7*8*9*10 
+ 11*12*13*14*15 = 365527.
Your Task:
You do not need to readd input or print anything. Your task is to complete the function sequence() which takes N as input parameter and returns the value of F(N).
Expected Tiime Complexity: O(N^{2})
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today your friends are playing a game of Exploding Kittens. On a player’s turn, she must perform the following actions in order:
 - Draw a single card from the top of the deck.
 - If the drawn card is an “Exploding Kitten”, she must leave the game unless she has a “Defuse” card in her hand, in which case she must discard both the “Exploding Kitten” card and the “Defuse” card, so that these two cards will never be drawn again in the same game. Otherwise, she can choose to do nothing.
 - If she has more than five cards in his hand, she must discard cards until he has no more than five cards.

Players alternate turns in a single round, and the relative orders in which players take turns must be identical between rounds. When a player leaves the game, the relative draw order of other players will stay the same. The last player left in the game is the winner, and the game will stop at that point.

You don’t want to watch the game because there’s no skill involved, but you still would like to know the result. You somehow know the location of all “Exploding Kittens” and “Defuse” cards in the deck. Assuming everyone starts with an empty hand and plays optimally (i.e. discard “Defuse” cards only when absolutely necessary), who will win the game?

-----Input-----
The first line consists of three integers $N$, the number of players in the game, $E$, the number of “Exploding Kitten” cards, and $D$, the number of “Defuse” cards. Note that $2\leq N\leq 1000$ and $2\leq D, E\leq 10000$.

The next line of the input contains $E$ integers $e_ i$ ($0\leq e_ i\leq 2\cdot 10^9$). This represents the number of cards between a “Exploding Kitten” card and the top card of the deck.

The final line of the input contains $D$ integers $d_ i$ ($0\leq d_ i\leq 2\cdot 10^9$). This represents the number of cards between a “Defuse” card and the top of the deck.

It is guaranteed that all “Exploding Kittens” and “Defuse” cards given in the input are located at distinct locations within the deck.

-----Output-----
If there is a winner, print the ID of the winner, defined as the number of players who took their turn before the winner on the first round. Otherwise, print $-1$.

-----Examples-----
Sample Input 1:
2 4 3
3 4 5 7
1 2 10
Sample Output 1:
0

Sample Input 2:
3 5 2
1 4 7 9 11
2 3
Sample Output 2:
2

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