vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Several years ago Tolya had n computer games and at some point of time he decided to burn them to CD. After that he wrote down the names of the games one after another in a circle on the CD in clockwise order. The names were distinct, the length of each name was equal to k. The names didn't overlap.

Thus, there is a cyclic string of length n·k written on the CD.

Several years have passed and now Tolya can't remember which games he burned to his CD. He knows that there were g popular games that days. All of the games he burned were among these g games, and no game was burned more than once.

You have to restore any valid list of games Tolya could burn to the CD several years ago.

Input

The first line of the input contains two positive integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 105) — the amount of games Tolya burned to the CD, and the length of each of the names.

The second line of the input contains one string consisting of lowercase English letters — the string Tolya wrote on the CD, split in arbitrary place. The length of the string is n·k. It is guaranteed that the length is not greater than 106.

The third line of the input contains one positive integer g (n ≤ g ≤ 105) — the amount of popular games that could be written on the CD. It is guaranteed that the total length of names of all popular games is not greater than 2·106.

Each of the next g lines contains a single string — the name of some popular game. Each name consists of lowercase English letters and has length k. It is guaranteed that the names are distinct.

Output

If there is no answer, print "NO" (without quotes).

Otherwise, print two lines. In the first line print "YES" (without quotes). In the second line, print n integers — the games which names were written on the CD. You should print games in the order they could have been written on the CD, it means, in clockwise order. You can print games starting from any position. Remember, that no game was burned to the CD more than once. If there are several possible answers, print any of them.

Examples

Input

3 1
abc
4
b
a
c
d


Output

YES
2 1 3 


Input

4 2
aabbccdd
4
dd
ab
bc
cd


Output

NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
IIIT-Delhi has been invaded by aliens. An alien race from a galaxy far away is shooting a beam on the Academic Block of IIIT-Delhi. Everyone is frightened by this attack. On each day a beam is shot on roof of Academic Block and there is great shaking in the block. IIIT-Delhi AlienAttack team has decided to make a layer to be put up on roof of the Academic block which can absorb this beam and thus protect the block from the beam. The AlienAttack team knows how to make this layer but for this they need to know the strength of beam falling on this layer. Babulal, guard of IIIT-Delhi has analysed the strength of beam and has found that the strength of beam on any day is the strength of beam on the previous day plus the twice the strength of beam on the day before previous day. Babulal then shared this analysis with the team. Now considering Babulal’s analysis AlienAttack team has to find the strength of the beam on Day N. So, consider yourself a part of the team and give the minimum strength that the layer should have to protect the block against the beam.     
Given the strength of beam on day one is 2 megapower and on day two is 7 megapower, you have to find the strength on day N.
As the value of strength on Day N can be very large print the result modulo 10^9 + 7.

Note :
1. Megapower is the unit of strength.
2. Building hasn't fallen down after the attack on first two days and after that you have to save the building.
3. Minimum strength of layer required on day N is equal to the strength of beam on day N.
4. Babulal’s analysis is correct, smart guard.
Input :
First line of input will contain a single integer T representing number of test cases.
Each of next T lines will contain a single integer N representing the day number of which you have to calculate the minimum strength of layer required.
Output :
Output will contain T lines each having a single integer representing the strength of beam on day N modulo 10^9 +7.
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 10^8

SAMPLE INPUT
2
3
4

SAMPLE OUTPUT
11
25

Explanation

Strength on day one is 2 and strength on day two is 7 so strength on day three is 7+22 i.e. 11 and on day four is 11+27 i.e. 25.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A substring is a string of characters that is contained in another string. For example, the substrings of "abcdef" could be "abc", "bc", "cdef", "e" and so on. But, "bca", "ace", and "g" are not substrings of "abcdef". 

Your task is to count the number of non-empty substrings possible of a given string such that all characters in that substring are same. If two substrings contains same alphabets but appear at different positions in that given string, they are still considered to be different. 

Input

A single string without spaces

Output

a single integer denoting the number of substrings as described above

Constraints
length of string will be between 1 and 100
all characters of string will be small case alphabets only

SAMPLE INPUT
xxxyx

SAMPLE OUTPUT
8

Explanation

four occurrences of substring "x"

one occurrence of substring "y"

two occurrences of substring "xx"  

one occurrence of substring "xxx"

= total 8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hackerman wants to know who is the better player between Bob and Alice with the help of a game.

The game proceeds as follows:
First, Alice throws a die and gets the number A
Then, Bob throws a die and gets the number B
Alice wins the game if the sum on the dice is a [prime number]; and Bob wins otherwise.

Given A and B, determine who wins the game.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains two space-separated integers A and B.

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

For each test case, output on a new line the winner of the game: Alice or Bob.

Each letter of the output may be printed in either uppercase or lowercase, i.e, Alice, ALICE, AlIce and aLIcE will all be considered equivalent.

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

$1 ≤ T ≤ 36$
$1 ≤ A ≤ 6$
$1 ≤ B ≤ 6$

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

----- Sample Output 1 ------ 
Alice
Alice
Bob

----- explanation 1 ------ 
Test case $1$: $A = 2$ and $B = 1$. Their sum is $2+1 = 3$ which is a prime number, so Alice wins.

Test case $2$: $A = 1$ and $B = 1$. Their sum is $1+1 = 2$ which is a prime number, so Alice wins.

Test case $3$: $A = 2$ and $B = 2$. Their sum is $2 + 2 = 4$ which is not a prime number, so Bob wins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

Chef is planning to setup a secure password for his Codechef account. For a password to be secure the following conditions should be satisfied:

1) Password must contain at least one lower case letter $[a-z]$;

2) Password must contain at least one upper case letter $[A-Z]$ strictly inside, i.e. not as the first or the last character;

3) Password must contain at least one digit $[0-9]$ strictly inside;

4) Password must contain at least one special character from the set $\{$ '@', '\#', '%', '&', '?' $\}$ strictly inside;

5) Password must be at least $10$ characters in length, but it can be longer.

Chef has generated several strings and now wants you to check whether the passwords are secure based on the above criteria. Please help Chef in doing so.

------  Input ------

First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains of a single line of input, string $S$. 

------  Output ------
For each testcase, output in a single line "YES" if the password is secure and "NO" if it is not.

------  Constraints  ------
$1 ≤ |S| ≤ 20$
All the characters in $S$ are one of the following: lower case letters $[a-z]$, upper case letters $[A-Z]$, digits $[0-9]$, special characters from the set $\{$ '@', '\#', '%', '&', '?' $\}$
Sum of length of strings over all tests is atmost $10^{6}$

----- Sample Input 1 ------ 
3

#cookOff#P1

U@code4CHEFINA

gR3@tPWD
----- Sample Output 1 ------ 
NO

YES

NO
----- explanation 1 ------ 
Example case 1: Condition $3$ is not satisfied, because the only digit is not strictly inside.

Example case 2: All conditions are satisfied.

Example case 3: Condition $5$ is not satisfied, because the length of this string is 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob play 5-in-a-row game. They have a playing field of size 10 × 10. In turns they put either crosses or noughts, one at a time. Alice puts crosses and Bob puts noughts.

In current match they have made some turns and now it's Alice's turn. She wonders if she can put cross in such empty cell that she wins immediately.

Alice wins if some crosses in the field form line of length not smaller than 5. This line can be horizontal, vertical and diagonal.


-----Input-----

You are given matrix 10 × 10 (10 lines of 10 characters each) with capital Latin letters 'X' being a cross, letters 'O' being a nought and '.' being an empty cell. The number of 'X' cells is equal to the number of 'O' cells and there is at least one of each type. There is at least one empty cell.

It is guaranteed that in the current arrangement nobody has still won.


-----Output-----

Print 'YES' if it's possible for Alice to win in one turn by putting cross in some empty cell. Otherwise print 'NO'.


-----Examples-----
Input
XX.XX.....
.....OOOO.
..........
..........
..........
..........
..........
..........
..........
..........

Output
YES

Input
XXOXX.....
OO.O......
..........
..........
..........
..........
..........
..........
..........
..........

Output
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive integer n.

Let S(x) be sum of digits in base 10 representation of x, for example, S(123) = 1 + 2 + 3 = 6, S(0) = 0.

Your task is to find two integers a, b, such that 0 ≤ a, b ≤ n, a + b = n and S(a) + S(b) is the largest possible among all such pairs.

Input

The only line of input contains an integer n (1 ≤ n ≤ 10^{12}).

Output

Print largest S(a) + S(b) among all pairs of integers a, b, such that 0 ≤ a, b ≤ n and a + b = n.

Examples

Input

35


Output

17


Input

10000000000


Output

91

Note

In the first example, you can choose, for example, a = 17 and b = 18, so that S(17) + S(18) = 1 + 7 + 1 + 8 = 17. It can be shown that it is impossible to get a larger answer.

In the second test example, you can choose, for example, a = 5000000001 and b = 4999999999, with S(5000000001) + S(4999999999) = 91. It can be shown that it is impossible to get a larger answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array A1,A2...AN, you have to print the size of the largest contiguous subarray such that 
GCD of all integers in that subarray is 1.

Formally,
For a subarray Ai,Ai+1...Aj where 1 ≤ i < j ≤ N to be valid: GCD(Ai,Ai+1...Aj) should be 1. You have to print the size of the largest valid subarray.
If no valid subarray exists, output -1.
Note:A single element is not considered as a subarray according to the definition of this problem.

-----Input-----
First line contains T, the number of testcases. Each testcase consists of N in one line followed by N integers in the next line.

-----Output-----
For each testcase, print the required answer in one line.

-----Constraints-----
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 105
- 1 ≤ Ai ≤ 105

-----Example-----
Input:
2
2
7 2
3
2 2 4

Output:
2
-1

-----Explanation-----
Example case 1.GCD(2,7)=1. So the subarray [A1,A2] is valid.
Example case 2.No subarray satisfies.
Note: Use scanf/print instead of cin/cout. Large input files.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Due to the COVID pandemic, maintaining social distancing is of utmost importance. In this problem, you'd calculate how many days would it take to reach an apocalypse from an initial case if nobody maintains social distancing.
The Earth is flat (for this question) and it's dimensions are $R$ x $C$
The whole Earth is already divided into blocks and the virus can spread in all directions except diagonally. The virus from each newly infected person will spread in all directions in the next day, thus growing exponentially.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Next line contains $R$ and $C$ respectively separated by a space.
- Next line contains $x$ and $y$ respectively separated by a space, denoting the indices of the initial case in the world.

-----Output:-----
For each testcase, output in a single line an integer denoting the number of days after which everyone will be infected.

-----Constraints-----
- $1 \leq T \leq 10^4$
- $2 \leq R,C \leq 10^7$
- $0 \leq x,y \leq 10^7$

-----Subtasks-----
- 10 points : $1 \leq T \leq 5$ and $2 \leq R,C \leq 10$
- 20 points : $2 \leq R,C \leq 10^5$
- 70 points : Original constraints

-----Sample Input:-----
2
4 5
2 1
3 4
1 1

-----Sample Output:-----
5
3

-----EXPLANATION:-----
2nd test case:
Assuming, it's a small world of $3$ x $4$
0 is not infected. 1 is infected.
World indexing is like a 2D array:
(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
If this is the case on Day 0:
0 0 0 0
0 1 0 0
0 0 0 0
This will be the case on Day 1:
0 1 0 0
1 1 1 0
0 1 0 0
This will be the case on Day 2:
1 1 1 0
1 1 1 1
1 1 1 0
The End on Day 3:
1 1 1 1
1 1 1 1
1 1 1 1
Thus, answer will be 3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a non-negative integer *n*, its decimal representation consists of at most 100 digits and doesn't contain leading zeroes.

Your task is to determine if it is possible in this case to remove some of the digits (possibly not remove any digit at all) so that the result contains at least one digit, forms a non-negative integer, doesn't have leading zeroes and is divisible by 8. After the removing, it is forbidden to rearrange the digits.

If a solution exists, you should print it.

Input Specification:
The single line of the input contains a non-negative integer *n*. The representation of number *n* doesn't contain any leading zeroes and its length doesn't exceed 100 digits.

Output Specification:
Print "NO" (without quotes), if there is no such way to remove some digits from number *n*. 

Otherwise, print "YES" in the first line and the resulting number after removing digits from number *n* in the second line. The printed number must be divisible by 8.

If there are multiple possible answers, you may print any of them.

Demo Input:
['3454\n', '10\n', '111111\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are the gym teacher in the school.

There are $n$ students in the row. And there are two rivalling students among them. The first one is in position $a$, the second in position $b$. Positions are numbered from $1$ to $n$ from left to right.

Since they are rivals, you want to maximize the distance between them. If students are in positions $p$ and $s$ respectively, then distance between them is $|p - s|$. 

You can do the following operation at most $x$ times: choose two adjacent (neighbouring) students and swap them.

Calculate the maximum distance between two rivalling students after at most $x$ swaps.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

The only line of each test case contains four integers $n$, $x$, $a$ and $b$ ($2 \le n \le 100$, $0 \le x \le 100$, $1 \le a, b \le n$, $a \neq b$) — the number of students in the row, the number of swaps which you can do, and positions of first and second rivaling students respectively.


-----Output-----

For each test case print one integer — the maximum distance between two rivaling students which you can obtain.


-----Example-----
Input
3
5 1 3 2
100 33 100 1
6 0 2 3

Output
2
99
1



-----Note-----

In the first test case you can swap students in positions $3$ and $4$. And then the distance between the rivals is equal to $|4 - 2| = 2$.

In the second test case you don't have to swap students. 

In the third test case you can't swap students.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two great friends, Eddie John and Kris Cross, are attending the Brackets Are Perfection Conference. They wholeheartedly agree with the main message of the conference and they are delighted with all the new things they learn about brackets.

One of these things is a bracket sequence. If you want to do a computation with $+$ and $\times $, you usually write it like so:\[ (2 \times (2 + 1 + 0 + 1) \times 1) + 3 + 2. \]

The brackets are only used to group multiplications and additions together. This means that you can remove all the operators, as long as you remember that addition is used for numbers outside any parentheses! A bracket sequence can then be shortened to\[ (\; 2 \; ( \; 2 \; 1 \; 0 \; 1 \; ) \; 1 \; ) \; 3 \; 2. \]

That is much better, because it saves on writing all those operators. Reading bracket sequences is easy, too. Suppose you have the following bracket sequence\[ 5 \; 2 \; (\; 3 \; 1 \; (\; 2 \; 2 \; ) \; ( \; 3 \; 3 \; ) \; 1 \; ). \]

You start with addition, so this is the same as the following:\[ 5 + 2 + (\; 3 \; 1 \; (\; 2 \; 2 \; ) \; ( \; 3 \; 3 \; ) \; 1 \; ). \]

You know the parentheses group a multiplication, so this is equal to\[ 5 + 2 + (3 \times 1 \times (\; 2 \; 2 \; ) \times ( \; 3 \; 3 \; ) \times 1). \]

Then there is another level of parentheses: that groups an operation within a multiplication, so the operation must be addition.\[ 5 + 2 + (3 \times 1 \times (2 + 2 ) \times (3 + 3) \times 1 ) = 5 + 2 + (3 \times 1 \times 4 \times 6 \times 1) = 5+2 + 72 = 79. \]

Since bracket sequences are so much easier than normal expressions with operators, it should be easy to evaluate some big ones. We will even allow you to write a program to do it for you.

Note that $(\; )$ is not a valid bracket sequence, nor a subsequence of any valid bracket sequence.

-----Input-----
 - One line containing a single integer $1\leq n\leq 3\cdot 10^5$.
 - One line consisting of $n$ tokens, each being either (, ), or an integer $0\leq x < 10^9+7$. It is guaranteed that the tokens form a bracket sequence.

-----Output-----
Output the value of the given bracket sequence. Since this may be very large, you should print it modulo $10^9+7$.

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

Sample Input 2:
8
( 2 ( 2 1 ) ) 3
Sample Output 2:
9

Sample Input 3:
4
( 12 3 )
Sample Output 3:
36

Sample Input 4:
6
( 2 ) ( 3 )
Sample Output 4:
5

Sample Input 5:
6
( ( 2 3 ) )
Sample Output 5:
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Next Wave Energy Research Club is looking at several atoms as potential energy sources, and has asked you to do some computations to see which are the most promising. 

Although an atom is composed of various parts, for the purposes of this method only the number of neutrons in the atom is relevant1. In the method, a laser charge is fired at the atom, which then releases energy in a process formally called explodification. Exactly how this process proceeds depends on the number of neutrons $k$:
 - If the atom contains $k \leq n$ neutrons, it will be converted into $a_ k$ joules of energy.
 - If the atom contains $k > n$ neutrons, it will decompose into two atoms with $i$ and $j$ neutrons respectively, satisfying $i,j \geq 1$ and $i+j=k$. These two atoms will then themselves explodificate.

When an atom with $k$ neutrons is explodificated, the total energy that is released depends on the exact sequence of decompositions that occurs in the explodification process. Modern physics is not powerful enough to predict exactly how an atom will decompose—however, for explodification to be a reliable energy source, we need to know the minimum amount of energy that it can release upon explodification. You have been tasked with computing this quantity.

-----Input-----
The input consists of:
 - One line with two integers $n$ and $q$ ($1 \leq n \leq 100$, $1 \leq q \leq 10^5$), the neutron threshold and the number of experiments.
 - One line with $n$ integers $a_1,\ldots ,a_ n$ ($1 \leq a_ i \leq 10^9$ for each $i$), where $a_ i$ is the amount of energy released when an atom with $i$ neutrons is explodificated.
 - Then $q$ lines follow, each with an integer $k$ ($1 \leq k \leq 10^9$), asking for the minimum energy released when an atom with $k$ neutrons is explodificated.

-----Output-----
For each query $k$, output the minimum energy released when an atom with $k$ neutrons is explodificated.

-----Examples-----
Sample Input:
4 5
2 3 5 7
2
3
5
6
8
Sample Output:
3
5
8
10
13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi the Jumbo will practice golf.
His objective is to get a carry distance that is a multiple of K, while he can only make a carry distance of between A and B (inclusive).
If he can achieve the objective, print OK; if he cannot, print NG.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq A \leq B \leq 1000
 - 1 \leq K \leq 1000

-----Input-----
Input is given from Standard Input in the following format:
K
A B

-----Output-----
If he can achieve the objective, print OK; if he cannot, print NG.

-----Sample Input-----
7
500 600

-----Sample Output-----
OK

Among the multiples of 7, for example, 567 lies between 500 and 600.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is constraints.

You are given $n$ segments on the coordinate axis $OX$. Segments can intersect, lie inside each other and even coincide. The $i$-th segment is $[l_i; r_i]$ ($l_i \le r_i$) and it covers all integer points $j$ such that $l_i \le j \le r_i$.

The integer point is called bad if it is covered by strictly more than $k$ segments.

Your task is to remove the minimum number of segments so that there are no bad points at all.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of segments and the maximum number of segments by which each integer point can be covered.

The next $n$ lines contain segments. The $i$-th line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le 2 \cdot 10^5$) — the endpoints of the $i$-th segment.


-----Output-----

In the first line print one integer $m$ ($0 \le m \le n$) — the minimum number of segments you need to remove so that there are no bad points.

In the second line print $m$ distinct integers $p_1, p_2, \dots, p_m$ ($1 \le p_i \le n$) — indices of segments you remove in any order. If there are multiple answers, you can print any of them.


-----Examples-----
Input
7 2
11 11
9 11
7 8
8 9
7 8
9 11
7 9

Output
3
4 6 7 

Input
5 1
29 30
30 30
29 29
28 30
30 30

Output
3
1 4 5 

Input
6 1
2 3
3 3
2 3
2 2
2 3
2 3

Output
4
1 3 5 6

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