vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given a string S of length N consisting of `A`, `C`, `G` and `T`. Answer the following Q queries:

* Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does `AC` occurs as a substring?

Constraints

* 2 \leq N \leq 10^5
* 1 \leq Q \leq 10^5
* S is a string of length N.
* Each character in S is `A`, `C`, `G` or `T`.
* 1 \leq l_i < r_i \leq N

Input

Input is given from Standard Input in the following format:


N Q
S
l_1 r_1
:
l_Q r_Q


Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Example

Input

8 3
ACACTACG
3 7
2 3
1 8


Output

2
0
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Vova found $n$ candy wrappers. He remembers that he bought $x$ candies during the first day, $2x$ candies during the second day, $4x$ candies during the third day, $\dots$, $2^{k-1} x$ candies during the $k$-th day. But there is an issue: Vova remembers neither $x$ nor $k$ but he is sure that $x$ and $k$ are positive integers and $k > 1$.

Vova will be satisfied if you tell him any positive integer $x$ so there is an integer $k>1$ that $x + 2x + 4x + \dots + 2^{k-1} x = n$. It is guaranteed that at least one solution exists. Note that $k > 1$.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains one integer $n$ ($3 \le n \le 10^9$) — the number of candy wrappers Vova found. It is guaranteed that there is some positive integer $x$ and integer $k>1$ that $x + 2x + 4x + \dots + 2^{k-1} x = n$.


-----Output-----

Print one integer — any positive integer value of $x$ so there is an integer $k>1$ that $x + 2x + 4x + \dots + 2^{k-1} x = n$.


-----Example-----
Input
7
3
6
7
21
28
999999999
999999984

Output
1
2
1
7
4
333333333
333333328



-----Note-----

In the first test case of the example, one of the possible answers is $x=1, k=2$. Then $1 \cdot 1 + 2 \cdot 1$ equals $n=3$.

In the second test case of the example, one of the possible answers is $x=2, k=2$. Then $1 \cdot 2 + 2 \cdot 2$ equals $n=6$.

In the third test case of the example, one of the possible answers is $x=1, k=3$. Then $1 \cdot 1 + 2 \cdot 1 + 4 \cdot 1$ equals $n=7$.

In the fourth test case of the example, one of the possible answers is $x=7, k=2$. Then $1 \cdot 7 + 2 \cdot 7$ equals $n=21$.

In the fifth test case of the example, one of the possible answers is $x=4, k=3$. Then $1 \cdot 4 + 2 \cdot 4 + 4 \cdot 4$ equals $n=28$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
I’m planning to have a party on my birthday. Many of my friends will come to the party. Some of them will come with one or more pieces of cakes, but it is not certain if the number of the cakes is a multiple of the number of people coming.

I wish to enjoy the cakes equally among the partiers. So, I decided to apply the following rules. First, all the party attendants are given the same number of cakes. If some remainder occurs, a piece goes on a priority basis to the party host (that’s me!). How many pieces of cake can I enjoy?

Given the number of my friends and cake information, make a program to calculate how many pieces of cake I can enjoy. Note that I am not counted in the number of my friends.



Input

The input is given in the following format.


$N$ $C$
$p_1$ $p_2$ ... $p_C$


The first line provides the number of my friends $N$ ($1 \leq N \leq 100$) and the number of those among them who brought one or more pieces of cake with them $C$ ($1 \leq C \leq N$). The second line provides an array of integers $p_i$ ($1 \leq p_i \leq100$), each of which shows the number of cakes of the $i$-th friend of mine who was willing to come up with one or more pieces of cake.

Output

Output the number of cakes I can enjoy.

Examples

Input

5 4
5 5 6 5


Output

4


Input

7 5
8 8 8 8 8


Output

5


Input

100 3
3 3 3


Output

1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Big P is willing to climb up a hill. The hill is divided into several checkpoints where the travelers can buy water,food etc for their trip.

At each checkpoint there are several roads that go up to other checkpoints (Not necessarily the next checkpoint).

Now Big P is standing at the base of the hill i.e at checkpoint 1 and wants to know the total number of ways he could climb to the top of the hill i.e the last checkpoint N.

Input Format:
First line contains an integer N,the total number of checkpoints on the hill. Next lines contain a pair of integers (x,y) denoting a directed path from checkpoint x to checkpoint y until a - (0 0) is in the input. 

Note: Base of Hill , where Big P is standing is Checkpoint #1 and the top of the hill is Checkpoint #N

Output Format:
A single integer X , denoting the total number of paths from the base of the hill to it's top.

[N ≤ 10000 , 1 ≤ x,y ≤ N]

SAMPLE INPUT
4
1 2
1 4
2 3
2 4
3 4
0 0

SAMPLE OUTPUT
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array $a$ of length $n$, find another array, $b$, of length $n$ such that:

  for each $i$ $(1 \le i \le n)$ $MEX(\{b_1$, $b_2$, $\ldots$, $b_i\})=a_i$. 

The $MEX$ of a set of integers is the smallest non-negative integer that doesn't belong to this set.

If such array doesn't exist, determine this.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($0 \le a_i \le i$) — the elements of the array $a$. It's guaranteed that $a_i \le a_{i+1}$ for $1\le i < n$. 


-----Output-----

If there's no such array, print a single line containing $-1$.

Otherwise, print a single line containing $n$ integers $b_1$, $b_2$, $\ldots$, $b_n$ ($0 \le b_i \le 10^6$)

If there are multiple answers, print any.


-----Examples-----
Input
3
1 2 3

Output
0 1 2 
Input
4
0 0 0 2

Output
1 3 4 0 
Input
3
1 1 3

Output
0 2 1 


-----Note-----

In the second test case, other answers like $[1,1,1,0]$, for example, are valid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the following experiment. You have a deck of m cards, and exactly one card is a joker. n times, you do the following: shuffle the deck, take the top card of the deck, look at it and return it into the deck.

Let x be the number of times you have taken the joker out of the deck during this experiment. Assuming that every time you shuffle the deck, all m! possible permutations of cards are equiprobable, what is the expected value of x^k? Print the answer modulo 998244353.

Input

The only line contains three integers n, m and k (1 ≤ n, m < 998244353, 1 ≤ k ≤ 5000).

Output

Print one integer — the expected value of x^k, taken modulo 998244353 (the answer can always be represented as an irreducible fraction a/b, where b mod 998244353 ≠ 0; you have to print a ⋅ b^{-1} mod 998244353).

Examples

Input


1 1 1


Output


1


Input


1 1 5000


Output


1


Input


2 2 2


Output


499122178


Input


998244352 1337 5000


Output


326459680

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are in charge of controlling a dam. The dam can store at most L liters of water. Initially, the dam is empty. Some amount of water flows into the dam every morning, and any amount of water may be discharged every night, but this amount needs to be set so that no water overflows the dam the next morning.
It is known that v_i liters of water at t_i degrees Celsius will flow into the dam on the morning of the i-th day.
You are wondering about the maximum possible temperature of water in the dam at noon of each day, under the condition that there needs to be exactly L liters of water in the dam at that time. For each i, find the maximum possible temperature of water in the dam at noon of the i-th day. Here, consider each maximization separately, that is, the amount of water discharged for the maximization of the temperature on the i-th day, may be different from the amount of water discharged for the maximization of the temperature on the j-th day (j≠i).
Also, assume that the temperature of water is not affected by anything but new water that flows into the dam. That is, when V_1 liters of water at T_1 degrees Celsius and V_2 liters of water at T_2 degrees Celsius are mixed together, they will become V_1+V_2 liters of water at \frac{T_1*V_1+T_2*V_2}{V_1+V_2} degrees Celsius, and the volume and temperature of water are not affected by any other factors.

-----Constraints-----
 - 1≤ N ≤ 5*10^5
 - 1≤ L ≤ 10^9
 - 0≤ t_i ≤ 10^9(1≤i≤N)
 - 1≤ v_i ≤ L(1≤i≤N)
 - v_1 = L
 - L, each t_i and v_i are integers.

-----Input-----
Input is given from Standard Input in the following format:
N L
t_1 v_1
t_2 v_2
:
t_N v_N

-----Output-----
Print N lines. The i-th line should contain the maximum temperature such that it is possible to store L liters of water at that temperature in the dam at noon of the i-th day.
Each of these values is accepted if the absolute or relative error is at most 10^{-6}.

-----Sample Input-----
3 10
10 10
20 5
4 3

-----Sample Output-----
10.0000000
15.0000000
13.2000000

 - On the first day, the temperature of water in the dam is always 10 degrees: the temperature of the only water that flows into the dam on the first day.
 - 10 liters of water at 15 degrees of Celsius can be stored on the second day, by discharging 5 liters of water on the night of the first day, and mix the remaining water with the water that flows into the dam on the second day.
 - 10 liters of water at 13.2 degrees of Celsius can be stored on the third day, by discharging 8 liters of water on the night of the first day, and mix the remaining water with the water that flows into the dam on the second and third days.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a binary string S of length N. You can perform the following operation on S:

Pick any set of indices such that no two picked indices are adjacent.
Flip the values at the picked indices (i.e. change 0 to 1 and 1 to 0).

For example, consider the string S = 1101101.  
If we pick the indices \{1,3,6\}, then after flipping the values at picked indices, we will get  \underline{1}1\underline{0}11\underline{0}1 \rightarrow 0111111.  
Note that we cannot pick the set \{2,3,5\} since 2 and 3 are adjacent indices.

Find the minimum number of operations required to convert all the characters of S to 0.

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

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the length of the binary string S.
- The second line of each test case contains a binary string S of length N.

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

For each test case, output the minimum number of operations required to convert all the characters of S to 0.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$

----- Sample Input 1 ------ 
3
6
101001
5
00000
3
111

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

----- explanation 1 ------ 
Test Case $1$: Pick the set of indices $\{1, 3, 6\}$. On flipping the values at these indices, the string becomes $000000$.

Test Case $2$: The string already has all characters equal to $0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bike is interested in permutations. A permutation of length n is an integer sequence such that each integer from 0 to (n - 1) appears exactly once in it. For example, [0, 2, 1] is a permutation of length 3 while both [0, 2, 2] and [1, 2, 3] is not.

A permutation triple of permutations of length n (a, b, c) is called a Lucky Permutation Triple if and only if $\forall i(1 \leq i \leq n), a_{i} + b_{i} \equiv c_{i} \operatorname{mod} n$. The sign a_{i} denotes the i-th element of permutation a. The modular equality described above denotes that the remainders after dividing a_{i} + b_{i} by n and dividing c_{i} by n are equal.

Now, he has an integer n and wants to find a Lucky Permutation Triple. Could you please help him?


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5).


-----Output-----

If no Lucky Permutation Triple of length n exists print -1.

Otherwise, you need to print three lines. Each line contains n space-seperated integers. The first line must contain permutation a, the second line — permutation b, the third — permutation c.

If there are multiple solutions, print any of them.


-----Examples-----
Input
5

Output
1 4 3 2 0
1 0 2 4 3
2 4 0 1 3

Input
2

Output
-1



-----Note-----

In Sample 1, the permutation triple ([1, 4, 3, 2, 0], [1, 0, 2, 4, 3], [2, 4, 0, 1, 3]) is Lucky Permutation Triple, as following holds:  $1 + 1 \equiv 2 \equiv 2 \operatorname{mod} 5$;  $4 + 0 \equiv 4 \equiv 4 \operatorname{mod} 5$;  $3 + 2 \equiv 0 \equiv 0 \operatorname{mod} 5$;  $2 + 4 \equiv 6 \equiv 1 \operatorname{mod} 5$;  $0 + 3 \equiv 3 \equiv 3 \operatorname{mod} 5$. 

In Sample 2, you can easily notice that no lucky permutation triple exists.

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

Chef and his friend Bharat have decided to play the game "The Chefora Spell".

In the game, a positive integer N (in decimal system) is considered a "Chefora" if the number of digits d is odd and it satisfies the equation N = \sum_{i=0}^{d-1} N_{i} \cdot 10^{i},

where N_{i} is the i-th digit of N from the left in 0-based indexing.

Let A_{i} denote the i-th smallest Chefora number.

They'll ask each other Q questions, where each question contains two integers L and R. The opponent then has to answer with

(\prod_{i=L+1}^R (A_{L})^{A_{i}}) \bmod{10^{9}+7}.

Bharat has answered all the questions right, and now it is Chef's turn. But since Chef fears that he could get some questions wrong, you have come to his rescue!

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

- The first line contains an integer Q - the number of questions Bharat asks.
- Each of the next Q lines contains two integers L and R.

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

Print Q integers - the answers to the questions on separate lines.

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

$1 ≤ Q ≤ 10^{5}$
$1 ≤ L < R ≤ 10^{5}$

------ subtasks ------ 

Subtask #1 (30 points):
$1 ≤ Q ≤ 5 \cdot 10^{3}$
$1 ≤ L < R ≤ 5 \cdot 10^{3}$

Subtask #2 (70 points): Original constraints

----- Sample Input 1 ------ 
2
1 2
9 11
----- Sample Output 1 ------ 
1
541416750
----- explanation 1 ------ 
- For the first question:
$$(A_{1})^{A_{2}}=1^{2}=1.$$

- For the second question:
$$(A_{9})^{A_{10}}\cdot (A_{9})^{A_{11}}=9^{101}\cdot 9^{111}\equiv 541416750 \pmod{10^{9}+7}.$$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a array A of size N. Lets see if you can find the maximum value of Ai % Aj such that Aj ≤ Ai and 1 ≤ i,j ≤ N.
Input

The first line contains integer N — the length of the sequence.

The second line contains N space-separated integers Ai
Output

Print the answer to the problem in one line
Constrains

1 ≤ N ≤ 5*10^5

1 ≤ ai ≤ 10^6

SAMPLE INPUT
3
3 4 5

SAMPLE OUTPUT
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: 2 + 2 != 4

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One very experienced problem writer decided to prepare a problem for April Fools Day contest. The task was very simple - given an arithmetic expression, return the result of evaluating this expression. However, looks like there is a bug in the reference solution...

Input Specification:
The only line of input data contains the arithmetic expression. The expression will contain between 2 and 10 operands, separated with arithmetic signs plus and/or minus. Each operand will be an integer between 0 and 255, inclusive.

Output Specification:
Reproduce the output of the reference solution, including the bug.

Demo Input:
['8-7+6-5+4-3+2-1-0\n', '2+2\n', '112-37\n']

Demo Output:
['4\n', '-46\n', '375\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Alyona is celebrating Happy Birthday! Her mother has an array of n flowers. Each flower has some mood, the mood of i-th flower is a_{i}. The mood can be positive, zero or negative.

Let's define a subarray as a segment of consecutive flowers. The mother suggested some set of subarrays. Alyona wants to choose several of the subarrays suggested by her mother. After that, each of the flowers will add to the girl's happiness its mood multiplied by the number of chosen subarrays the flower is in.

For example, consider the case when the mother has 5 flowers, and their moods are equal to 1,  - 2, 1, 3,  - 4. Suppose the mother suggested subarrays (1,  - 2), (3,  - 4), (1, 3), (1,  - 2, 1, 3). Then if the girl chooses the third and the fourth subarrays then:   the first flower adds 1·1 = 1 to the girl's happiness, because he is in one of chosen subarrays,  the second flower adds ( - 2)·1 =  - 2, because he is in one of chosen subarrays,  the third flower adds 1·2 = 2, because he is in two of chosen subarrays,  the fourth flower adds 3·2 = 6, because he is in two of chosen subarrays,  the fifth flower adds ( - 4)·0 = 0, because he is in no chosen subarrays. 

Thus, in total 1 + ( - 2) + 2 + 6 + 0 = 7 is added to the girl's happiness. Alyona wants to choose such subarrays from those suggested by the mother that the value added to her happiness would be as large as possible. Help her do this!

Alyona can choose any number of the subarrays, even 0 or all suggested by her mother.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of flowers and the number of subarrays suggested by the mother.

The second line contains the flowers moods — n integers a_1, a_2, ..., a_{n} ( - 100 ≤ a_{i} ≤ 100).

The next m lines contain the description of the subarrays suggested by the mother. The i-th of these lines contain two integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n) denoting the subarray a[l_{i}], a[l_{i} + 1], ..., a[r_{i}].

Each subarray can encounter more than once.


-----Output-----

Print single integer — the maximum possible value added to the Alyona's happiness.


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

Output
7

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

Output
16

Input
2 2
-1 -2
1 1
1 2

Output
0



-----Note-----

The first example is the situation described in the statements.

In the second example Alyona should choose all subarrays.

The third example has answer 0 because Alyona can choose none of the subarrays.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mad scientist Mike has just finished constructing a new device to search for extraterrestrial intelligence! He was in such a hurry to launch it for the first time that he plugged in the power wires without giving it a proper glance and started experimenting right away. After a while Mike observed that the wires ended up entangled and now have to be untangled again.

The device is powered by two wires "plus" and "minus". The wires run along the floor from the wall (on the left) to the device (on the right). Both the wall and the device have two contacts in them on the same level, into which the wires are plugged in some order. The wires are considered entangled if there are one or more places where one wire runs above the other one. For example, the picture below has four such places (top view): [Image] 

Mike knows the sequence in which the wires run above each other. Mike also noticed that on the left side, the "plus" wire is always plugged into the top contact (as seen on the picture). He would like to untangle the wires without unplugging them and without moving the device. Determine if it is possible to do that. A wire can be freely moved and stretched on the floor, but cannot be cut.

To understand the problem better please read the notes to the test samples.


-----Input-----

The single line of the input contains a sequence of characters "+" and "-" of length n (1 ≤ n ≤ 100000). The i-th (1 ≤ i ≤ n) position of the sequence contains the character "+", if on the i-th step from the wall the "plus" wire runs above the "minus" wire, and the character "-" otherwise.


-----Output-----

Print either "Yes" (without the quotes) if the wires can be untangled or "No" (without the quotes) if the wires cannot be untangled.


-----Examples-----
Input
-++-

Output
Yes

Input
+-

Output
No

Input
++

Output
Yes

Input
-

Output
No



-----Note-----

The first testcase corresponds to the picture in the statement. To untangle the wires, one can first move the "plus" wire lower, thus eliminating the two crosses in the middle, and then draw it under the "minus" wire, eliminating also the remaining two crosses.

In the second testcase the "plus" wire makes one full revolution around the "minus" wire. Thus the wires cannot be untangled:  [Image] 

In the third testcase the "plus" wire simply runs above the "minus" wire twice in sequence. The wires can be untangled by lifting "plus" and moving it higher:  [Image] 

In the fourth testcase the "minus" wire runs above the "plus" wire once. The wires cannot be untangled without moving the device itself:  [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The integer numbers from 1 to nm was put into rectangular table having n rows and m columns. The numbers was put from left to right, from top to bottom, i.e. the first row contains integers 1, 2, ..., m, the second — m + 1, m + 2, ..., 2 * m and so on.

After it these numbers was written on the paper in another order: from top to bottom, from left to right. First, the numbers in the first column was written (from top to bottom) and so on.

Print the k-th number on the paper.

Input

The only line in the input contains three integer numbers n, m and k (1 ≤ n, m ≤ 20000, 1 ≤ k ≤ nm).

Output

Print the required number.

Examples

Input

3 4 11


Output

8


Input

20000 10000 200000000


Output

200000000

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