vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There is a colony of villains with several holes aligned in a row, where each hole contains exactly one villain.

Each colony arrangement can be expressed as a string of even length, where the i-th character of the string represents the type of villain in the i-th hole. 

Iron Man can destroy a colony only if the colony arrangement is such that all villains of a certain type either live in the first half of the colony or in the second half of the colony.

His assistant Jarvis has a special power. It can swap villains of any two holes, i.e. swap any two characters in the string; he can do this operation any number of times.

Now Iron Man asks Jarvis q questions. In each question, he gives Jarvis two numbers x and y. Jarvis has to tell Iron Man the number of distinct colony arrangements he can create from the original one using his powers such that all villains having the same type as those originally living in x-th hole or y-th hole live in the same half and the Iron Man can destroy that colony arrangement.

Two colony arrangements are considered to be different if there exists a hole such that different types of villains are present in that hole in the arrangements.

Input

The first line contains a string s (2 ≤ |s| ≤ 10^{5}), representing the initial colony arrangement. String s can have both lowercase and uppercase English letters and its length is even.

The second line contains a single integer q (1 ≤ q ≤ 10^{5}) — the number of questions.

The i-th of the next q lines contains two integers x_i and y_i (1 ≤ x_i, y_i ≤ |s|, x_i ≠ y_i) — the two numbers given to the Jarvis for the i-th question.

Output

For each question output the number of arrangements possible modulo 10^9+7.

Examples

Input


abba
2
1 4
1 2


Output


2
0


Input


AAaa
2
1 2
1 3


Output


2
0


Input


abcd
1
1 3


Output


8

Note

Consider the first example. For the first question, the possible arrangements are "aabb" and "bbaa", and for the second question, index 1 contains 'a' and index 2 contains 'b' and there is no valid arrangement in which all 'a' and 'b' are in the same half.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string you need to print the size of the longest possible substring that has exactly K unique characters. If there is no possible substring then print -1.
Example 1:
Input:
S = "aabacbebebe", K = 3
Output: 7
Explanation: "cbebebe" is the longest 
substring with K distinct characters.
Example 2:
Input: 
S = "aaaa", K = 2
Output: -1
Explanation: There's no substring with K
distinct characters.
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestKSubstr() which takes the string S and an integer K as input and returns the length of the longest substring with exactly K distinct characters. If there is no substring with exactly K distinct characters then return -1.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|).
Constraints:
1 ≤ |S| ≤ 10^{5}
1 ≤ K ≤ 10^{5}
All characters are lowercase latin characters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Unfortunately, Vasya can only sum pairs of integers (a, b), such that for any decimal place at least one number has digit 0 in this place. For example, Vasya can sum numbers 505 and 50, but he cannot sum 1 and 4.

Vasya has a set of k distinct non-negative integers d_1, d_2, ..., d_{k}.

Vasya wants to choose some integers from this set so that he could sum any two chosen numbers. What maximal number of integers can he choose in the required manner?


-----Input-----

The first input line contains integer k (1 ≤ k ≤ 100) — the number of integers.

The second line contains k distinct space-separated integers d_1, d_2, ..., d_{k} (0 ≤ d_{i} ≤ 100).


-----Output-----

In the first line print a single integer n the maximum number of the chosen integers. In the second line print n distinct non-negative integers — the required integers.

If there are multiple solutions, print any of them. You can print the numbers in any order.


-----Examples-----
Input
4
100 10 1 0

Output
4
0 1 10 100 
Input
3
2 70 3

Output
2
2 70

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Monk and his P-1 friends recently joined a college. He finds that N students have already applied for different courses before him.  Courses are assigned numbers from 1 to C. He and his friends will follow the following conditions when choosing courses:- 
They will choose the course i (1 ≤ i ≤ C), for which the value of z is minimum. Here, z = x*c where c is the number of students already enrolled in the course i and  x is the sum of IQ of the last two students who enrolled in that course. If a single student has applied for a course, then the value of x will be that student's IQ. If no student has enrolled for that course, then value of x will be 0. If the value of z is same for two courses, then they will choose the course with the minimum course number. You need to find which courses Monk and his friends should take after following the above conditions.
Note: Each of them will choose their courses, one at a time. Monk will choose his course first followed by his friends.

Input:
The first line contains the numbers C, P and N where C denotes the number of courses in that college, P denotes Monk and his friends and N denotes the number of students who have already applied for the courses.
The next line consists of N space separated integers Y[i] which denotes the IQ of the i^th student. Here, the i^th  student chooses the i^th course.  
The next line consists of P space separated integers X[i] which denotes the IQ of Monk and his friends.

Output:
Print P space separated integers in a line which denotes the course number which Monk and his friends have applied for.

Constraints:
1 ≤ C ≤ 100000
1 ≤ P ≤ 100000
1 ≤ N ≤ C
1 ≤ Y[i],X[i] ≤ 100000

SAMPLE INPUT
5 4 4
2 8 5 1
9 10 5 1

SAMPLE OUTPUT
5 4 1 3 

Explanation

In the sample test case, the last course has not been applied by anyone. So, its sum will be 0 initially. Hence, Monk will apply there as the value of z = 0.
Now Monk's first friend will apply for the 4th course as its value of z = 1, which is minimum of all the four courses.
Monk's second friend will apply for the 1st course as its value of z = 2, which is minimum of all the four courses.
Similarly, Monk's third friend will apply for the 3rd course as its value of z = 5, which is minimum of all the four courses.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call a string "s-palindrome" if it is symmetric about the middle of the string. For example, the string "oHo" is "s-palindrome", but the string "aa" is not. The string "aa" is not "s-palindrome", because the second half of it is not a mirror reflection of the first half.

<image> English alphabet

You are given a string s. Check if the string is "s-palindrome".

Input

The only line contains the string s (1 ≤ |s| ≤ 1000) which consists of only English letters.

Output

Print "TAK" if the string s is "s-palindrome" and "NIE" otherwise.

Examples

Input

oXoxoXo


Output

TAK


Input

bod


Output

TAK


Input

ER


Output

NIE

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko buys a lot of candy in the candy shop. He cannot always pay the exact amount so the shopkeeper and he have an agreement. He tells the shopkeeper the smallest bill he has, and she rounds his amount to the nearest number he can pay. For example, if the smallest bill Mirko has is a hundred bill, and he wants to buy $150$ Kunas of candy, the shopkeeper rounds his amount to $200$ Kunas. If he wants to buy $149$ Kunas of candy, the shopkeeper rounds his amount to $100$ Kunas.

Lately, Mirko suspects the shoopkeeper is trying to cheat him. He asked you to help him. Write a program that will help him. His mother only gives Mirko $1, 10, 100, 1000, \ldots , 1000000000$ Kuna bills. He never has bills that are not powers of $10$. The bills he does have, he has in large amounts.

-----Input-----
The first and only line of input contains two integers, $C$ ($0 \le C \le 1000000000$), the price of candy Mirko is going to buy, and $K$ ($0 \le K \le 9$), number of zeros on the smallest bill Mirko has.

-----Output-----
The first and only line of output should contain one integer, $C$ rounded to the nearest amount Mirko can pay.

-----Examples-----
Sample Input 1:
184 1
Sample Output 1:
180

Sample Input 2:
123450995 1
Sample Output 2:
123451000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Maya is teaching Alex about HyperText Markup Language (HTML). Alex is confused about div and span tags, so Maya decides to reduce the concept to a simpler visual by representing div tags as square brackets and span tags as parentheses. In other words, she represents <div> as [, </div> as ], <span> as (, and </span> as ).

We use the following rules to determine the validity of a configuration:

The empty string (""), a single pair of square brackets [], and single pair of parentheses () are all considered to be valid configurations. We can express each of these as ${V}$.
A valid configuration, ${V}$, which does not contain square brackets is called a normal configuration, which we can express as $N$. For example, () is normal.
Two or more consecutive valid configurations (e.g., ${VV}$) also constitute a valid configuration. For example, [][], ()(), and []()[] are all valid.
The following configurations are also valid: [V], (N). 

For example, [[(())]()], ((())), and [(())[]] are all valid; however, ([]) is not valid (you cannot nest a div tag inside a span tag).

Given some number of distinguishable square brackets, ${X}$, and some number of distinguishable parentheses, ${Y}$, how many valid configurations can we build using the above rules? As this answer can be very large, print it modulo $10^9+7$.

Input Format

The first line contains a single positive integer, ${T}$, denoting the number of test cases. 

Each of the ${T}$ subsequent lines contains $2$ positive space-separated integers describing the respective values of ${X}$ (the number of distinguishable square brackets) and $Y$ (the number of distinguishable parentheses).

Constraints

$1\leq T\leq1000$
$1\leq X\leq10^5$
$1\leq Y\leq200$

Output Format

For each test case, print the number of different valid configurations modulo $10^9+7$.

Sample Input
3
1 1
1 2
2 2

Sample Output
3
18
160

Explanation

For the first test case, $X=1$, $Y=1$, these are $3$ valid configurations: 

[]()
()[]
[()]

Thus, we print the result of $3\%(10^9+7)$ on the first line.

For the second test case, if brackets and parentheses were not distinguishable, we would have only $\mbox{9}$ different configurations:

[()]() []()() [](())
()[]() [()()] [(())]
()()[] ()[()] (())[]

However, they are distinguishable, so [](1)(2) is not same as [](2)(1) (where (1) and (2) are the respective first and second pairs of parentheses. For this reason, we have $18}$ possible configurations and print the result of $18\%(10^9+7)$ on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the infinite x$x$ axis. There are N$N$ impacts on this X-axis at integral points (X1$X_1$,X2$X_2$,....XN$X_N$)  (all distinct) . An impact at a point X$X$i propagates such that at a point X$X$0, the effect of the impact is K|Xi−X0|$K^{|X_i - X_0|}$. Given the point X0$X_0$, N$N$ and K$K$. Assume the total impact on X0$X_0$ is M$M$, find if it is possible to do so.Note: You are not required to find the set X

Formally print "yes" if this is possible and "no" if not possible.

-----Input:-----
- First line will contain T$T$, number of testcases. Then the testcases follow. 
-  Each testcase contains of a single line of input, four integers N$N$,K$K$,M$M$,X$X$0 

-----Output:-----
-  The output of each test case is either "yes" or "no"

-----Constraints -----
-  1≤T≤1000$1\leq T \leq 1000$
-  1≤N≤100$1\leq N \leq 100$
-  1≤K≤1000$1\leq K \leq 1000$
-  1≤M≤1018$1\leq M \leq 10^{18}$
-  −109≤X0≤109$-10^9 \leq X_0 \leq 10^9$ 

-----Sample Input:-----
	2

4 3 10 10

2 3 10 10

-----Sample Output:-----
	no

yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasiliy likes to rest after a hard work, so you may often meet him in some bar nearby. As all programmers do, he loves the famous drink "Beecola", which can be bought in n different shops in the city. It's known that the price of one bottle in the shop i is equal to x_{i} coins.

Vasiliy plans to buy his favorite drink for q consecutive days. He knows, that on the i-th day he will be able to spent m_{i} coins. Now, for each of the days he want to know in how many different shops he can buy a bottle of "Beecola".


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of shops in the city that sell Vasiliy's favourite drink.

The second line contains n integers x_{i} (1 ≤ x_{i} ≤ 100 000) — prices of the bottles of the drink in the i-th shop.

The third line contains a single integer q (1 ≤ q ≤ 100 000) — the number of days Vasiliy plans to buy the drink.

Then follow q lines each containing one integer m_{i} (1 ≤ m_{i} ≤ 10^9) — the number of coins Vasiliy can spent on the i-th day.


-----Output-----

Print q integers. The i-th of them should be equal to the number of shops where Vasiliy will be able to buy a bottle of the drink on the i-th day.


-----Example-----
Input
5
3 10 8 6 11
4
1
10
3
11

Output
0
4
1
5



-----Note-----

On the first day, Vasiliy won't be able to buy a drink in any of the shops.

On the second day, Vasiliy can buy a drink in the shops 1, 2, 3 and 4.

On the third day, Vasiliy can buy a drink only in the shop number 1.

Finally, on the last day Vasiliy can buy a drink in any shop.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
This is the modification of the problem used during the official round. Unfortunately, author's solution of the original problem appeared wrong, so the problem was changed specially for the archive.

Once upon a time in a far away kingdom lived the King. The King had a beautiful daughter, Victoria. They lived happily, but not happily ever after: one day a vicious dragon attacked the kingdom and stole Victoria. The King was full of grief, yet he gathered his noble knights and promised half of his kingdom and Victoria's hand in marriage to the one who will save the girl from the infernal beast.

Having travelled for some time, the knights found the dragon's lair and all of them rushed there to save Victoria. Each knight spat on the dragon once and, as the dragon had quite a fragile and frail heart, his heart broke and poor beast died. As for the noble knights, they got Victoria right to the King and started brawling as each one wanted the girl's hand in marriage.

The problem was that all the noble knights were equally noble and equally handsome, and Victoria didn't want to marry any of them anyway. Then the King (and he was a very wise man and didn't want to hurt anybody's feelings) decided to find out who will get his daughter randomly, i.e. tossing a coin. However, there turned out to be *n* noble knights and the coin only has two sides. The good thing is that when a coin is tossed, the coin falls on each side with equal probability. The King got interested how to pick one noble knight using this coin so that all knights had equal probability of being chosen (the probability in that case should always be equal to 1<=/<=*n*). First the King wants to know the expected number of times he will need to toss a coin to determine the winner. Besides, while tossing the coin, the King should follow the optimal tossing strategy (i.e. the strategy that minimizes the expected number of tosses). Help the King in this challenging task.

Input Specification:
The first line contains a single integer *n* from the problem's statement (1<=≤<=*n*<=≤<=10000).

Output Specification:
Print the sought expected number of tosses as an irreducible fraction in the following form: "*a*/*b*" (without the quotes) without leading zeroes.

Demo Input:
['2\n', '3\n', '4\n']

Demo Output:
['1/1\n', '8/3\n', '2/1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr of size N with all initial values as 0, the task is to perform the following M range increment operations as shown below: 
Increment(a_{i}, b_{i}, k_{i}) : Increment values from index 'a_{i}' to 'b_{i}' by 'k_{i}'.
After M operations, calculate the maximum value in the array arr[].
Example 1:
Input: N = 5, M = 3, a[] = {0, 1, 2}
b[] = {1, 4, 3}, k[] = {100, 100, 100}
Output: 200
Explanation: Initially array = {0, 0, 0, 
                                   0, 0}
After first operation : {100, 100, 0, 0, 0}
After second operation: {100, 200, 100, 100, 100}
After third operation: {100, 200, 200, 200, 100}
Maximum element after m operations is 200.
Example 2:
Input: N = 4, M = 3, a[] = {1, 0, 3} 
b[] = {2, 0, 3}, k[] = {603, 286, 882}
Output: 882
Explanation: Initially array = {0, 0, 0, 0}
After first operation: {0, 603, 603, 0}
After second operation: {286, 603, 603, 0}
After third operation: {286, 603, 603, 882}
Maximum element after m operations is 882.
Your Task:
You don't need to read input or print anything. You just need to complete the function findMax() that takes arrays a[], b[], k[] and integers N, M as parameters and returns the desired output.
 
Expected Time Complexity: O(M+N).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{6}
0 ≤ a_{i } ≤ b_{i} ≤ N-1
1 ≤ M ≤ 10^{6}
0 ≤ k_{i} ≤ 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mahmoud has an array a consisting of n integers. He asked Ehab to find another array b of the same length such that:

  b is lexicographically greater than or equal to a.  b_{i} ≥ 2.  b is pairwise coprime: for every 1 ≤ i < j ≤ n, b_{i} and b_{j} are coprime, i. e. GCD(b_{i}, b_{j}) = 1, where GCD(w, z) is the greatest common divisor of w and z. 

Ehab wants to choose a special array so he wants the lexicographically minimal array between all the variants. Can you find it?

An array x is lexicographically greater than an array y if there exists an index i such than x_{i} > y_{i} and x_{j} = y_{j} for all 1 ≤ j < i. An array x is equal to an array y if x_{i} = y_{i} for all 1 ≤ i ≤ n.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 10^5), the number of elements in a and b.

The second line contains n integers a_1, a_2, ..., a_{n} (2 ≤ a_{i} ≤ 10^5), the elements of a.


-----Output-----

Output n space-separated integers, the i-th of them representing b_{i}.


-----Examples-----
Input
5
2 3 5 4 13

Output
2 3 5 7 11 
Input
3
10 3 7

Output
10 3 7 


-----Note-----

Note that in the second sample, the array is already pairwise coprime so we printed it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are at your grandparents' house and you are playing an old video game on a strange console. Your controller has only two buttons and each button has a number written on it.

Initially, your score is $0$. The game is composed of $n$ rounds. For each $1\le i\le n$, the $i$-th round works as follows.

On the screen, a symbol $s_i$ appears, which is either ${+}$ (plus) or ${-}$ (minus). Then you must press one of the two buttons on the controller once. Suppose you press a button with the number $x$ written on it: your score will increase by $x$ if the symbol was ${+}$ and will decrease by $x$ if the symbol was ${-}$. After you press the button, the round ends.

After you have played all $n$ rounds, you win if your score is $0$.

Over the years, your grandparents bought many different controllers, so you have $q$ of them. The two buttons on the $j$-th controller have the numbers $a_j$ and $b_j$ written on them. For each controller, you must compute whether you can win the game playing with that controller.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2\cdot 10^5$) — the number of rounds.

The second line contains a string $s$ of length $n$ — where $s_i$ is the symbol that will appear on the screen in the $i$-th round. It is guaranteed that $s$ contains only the characters ${+}$ and ${-}$.

The third line contains an integer $q$ ($1 \le q \le 10^5$) — the number of controllers.

The following $q$ lines contain two integers $a_j$ and $b_j$ each ($1 \le a_j, b_j \le 10^9$) — the numbers on the buttons of controller $j$.


-----Output-----

Output $q$ lines. On line $j$ print ${YES}$ if the game is winnable using controller $j$, otherwise print ${NO}$.


-----Examples-----

Input
8
+-+---+-
5
2 1
10 3
7 9
10 10
5 3
Output
YES
NO
NO
NO
YES
Input
6
+-++--
2
9 7
1 1
Output
YES
YES
Input
20
+-----+--+--------+-
2
1000000000 99999997
250000000 1000000000
Output
NO
YES


-----Note-----

In the first sample, one possible way to get score $0$ using the first controller is by pressing the button with numnber $1$ in rounds $1$, $2$, $4$, $5$, $6$ and $8$, and pressing the button with number $2$ in rounds $3$ and $7$. It is possible to show that there is no way to get a score of $0$ using the second controller.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nimbus, techfest of NIT Hamipur is going on and Team.exe (departmental team of CSE) is organizing an event called codeswap. Codeswap is a team event containing 3 members in a team. 

Now, one of the 3 members of the team is given a number D and the other member is given a number R. Now, the third member is given a number N such that (N-R) % D = 0. 

You are given the numbers N, D and R and you have to find the number of permutations of N such that the equation

(N-R) % D = 0 is satisfied. It is possible that there exist zero permutations of N which satisfies the above equation.

NOTE- if N=3009 then 0093 (containing leading zeros) is a valid permutation of N.  

INPUT

The input contains 3 integers N, D, R, denoting variables as mentioned in the problem statement.

OUTPUT

The output should contain a single integer with a newline character at end.

CONSTRAINTS

0 ≤ N ≤ 10^14

1 ≤ D ≤ 1000

0 ≤ R ≤ D-1

SAMPLE INPUT
214 2 0

SAMPLE OUTPUT
4

Explanation

214 has 6 permutations. Out of these the valid permutations are 124 , 142 , 214 , 412

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese  and Russian. 
Sereja has an array A that contains n integers: A_{1}, A_{2}, ..., A_{n}. 
Sereja also has an array B that contains n integers B_{1}, B_{2}, ..., B_{n}. 
In a single step Sereja can choose two indexes i and j (1 ≤ i ≤ j ≤ n) , and increase all the elements of A with indices between i and j inclusively by one, modulo 4.
In other words, we make A_{p} equal to (A_{p} + 1) modulo 4 if p is an integer from the range [i; j].

Now Sereja is interested in the following question: what is the mininal number of steps necessary in order to make the array A equal to the array B.

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

The first line contains an integer T - the number of the testcases. Then, T tests follow. 

The first line of each testcase contains the integer n. 

The next line conatins n single space separated integers - A_{1}, A_{2}, ..., A_{n}. 

The next line conatin n single space separated integers - B_{1}, B_{2}, ..., B_{n}.

------ Output ------ 

For each testcase output an answer - the mininal number of steps necessary.

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

$1 ≤ T ≤ 10$
$1 ≤ n ≤ 10^{5}$
$0 ≤ A_{i}, B_{i} ≤ 3$

------ Example ------ 

Input:
1
5
2 1 3 0 3
2 2 0 1 0

Output:
1

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