vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Gildong recently learned how to find the longest increasing subsequence (LIS) in $O(n\log{n})$ time for a sequence of length $n$. He wants to test himself if he can implement it correctly, but he couldn't find any online judges that would do it (even though there are actually many of them). So instead he's going to make a quiz for you about making permutations of $n$ distinct integers between $1$ and $n$, inclusive, to test his code with your output.

The quiz is as follows.

Gildong provides a string of length $n-1$, consisting of characters '<' and '>' only. The $i$-th (1-indexed) character is the comparison result between the $i$-th element and the $i+1$-st element of the sequence. If the $i$-th character of the string is '<', then the $i$-th element of the sequence is less than the $i+1$-st element. If the $i$-th character of the string is '>', then the $i$-th element of the sequence is greater than the $i+1$-st element.

He wants you to find two possible sequences (not necessarily distinct) consisting of $n$ distinct integers between $1$ and $n$, inclusive, each satisfying the comparison results, where the length of the LIS of the first sequence is minimum possible, and the length of the LIS of the second sequence is maximum possible.


-----Input-----

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$).

Each test case contains exactly one line, consisting of an integer and a string consisting of characters '<' and '>' only. The integer is $n$ ($2 \le n \le 2 \cdot 10^5$), the length of the permutation you need to find. The string is the comparison results explained in the description. The length of the string is $n-1$.

It is guaranteed that the sum of all $n$ in all test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print two lines with $n$ integers each. The first line is the sequence with the minimum length of the LIS, and the second line is the sequence with the maximum length of the LIS. If there are multiple answers, print any one of them. Each sequence should contain all integers between $1$ and $n$, inclusive, and should satisfy the comparison results.

It can be shown that at least one answer always exists.


-----Example-----
Input
3
3 <<
7 >><>><
5 >>><

Output
1 2 3
1 2 3
5 4 3 7 2 1 6
4 3 1 7 5 2 6
4 3 2 1 5
5 4 2 1 3



-----Note-----

In the first case, $1$ $2$ $3$ is the only possible answer.

In the second case, the shortest length of the LIS is $2$, and the longest length of the LIS is $3$. In the example of the maximum LIS sequence, $4$ '$3$' $1$ $7$ '$5$' $2$ '$6$' can be one of the possible LIS.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a harder version of the problem E with larger constraints.

Twilight Sparkle has received a new task from Princess Celestia. This time she asked to decipher the ancient scroll containing important knowledge of pony origin.

To hide the crucial information from evil eyes, pony elders cast a spell on the scroll. That spell adds exactly one letter in any place to each word it is cast on. To make the path to the knowledge more tangled elders chose some of words in the scroll and cast a spell on them.

Twilight Sparkle knows that the elders admired the order in all things so the scroll original scroll contained words in lexicographically non-decreasing order. She is asked to delete one letter from some of the words of the scroll (to undo the spell) to get some version of the original scroll. 

Unfortunately, there may be more than one way to recover the ancient scroll. To not let the important knowledge slip by Twilight has to look through all variants of the original scroll and find the required one. To estimate the maximum time Twilight may spend on the work she needs to know the number of variants she has to look through. She asks you to find that number! Since that number can be very big, Twilight asks you to find it modulo 10^9+7.

It may occur that princess Celestia has sent a wrong scroll so the answer may not exist.

A string a is lexicographically smaller than a string b if and only if one of the following holds:

  * a is a prefix of b, but a ≠ b;
  * in the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5): the number of words in the scroll.

The i-th of the next n lines contains a string consisting of lowercase English letters: the i-th word in the scroll. The length of each word is at least one. The sum of lengths of words does not exceed 10^6.

Output

Print one integer: the number of ways to get a version of the original from the scroll modulo 10^9+7.

Examples

Input


3
abcd
zaza
ataka


Output


4


Input


4
dfs
bfs
sms
mms


Output


8


Input


3
abc
bcd
a


Output


0


Input


6
lapochka
kartyshka
bigbabytape
morgenshtern
ssshhhiiittt
queen


Output


2028

Note

Notice that the elders could have written an empty word (but they surely cast a spell on it so it holds a length 1 now).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vanya smashes potato in a vertical food processor. At each moment of time the height of the potato in the processor doesn't exceed h and the processor smashes k centimeters of potato each second. If there are less than k centimeters remaining, than during this second processor smashes all the remaining potato.

Vanya has n pieces of potato, the height of the i-th piece is equal to a_{i}. He puts them in the food processor one by one starting from the piece number 1 and finishing with piece number n. Formally, each second the following happens:

  If there is at least one piece of potato remaining, Vanya puts them in the processor one by one, until there is not enough space for the next piece.  Processor smashes k centimeters of potato (or just everything that is inside). 

Provided the information about the parameter of the food processor and the size of each potato in a row, compute how long will it take for all the potato to become smashed.


-----Input-----

The first line of the input contains integers n, h and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ h ≤ 10^9) — the number of pieces of potato, the height of the food processor and the amount of potato being smashed each second, respectively.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ h) — the heights of the pieces.


-----Output-----

Print a single integer — the number of seconds required to smash all the potatoes following the process described in the problem statement.


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

Output
5

Input
5 6 3
5 5 5 5 5

Output
10

Input
5 6 3
1 2 1 1 1

Output
2



-----Note-----

Consider the first sample.   First Vanya puts the piece of potato of height 5 into processor. At the end of the second there is only amount of height 2 remaining inside.  Now Vanya puts the piece of potato of height 4. At the end of the second there is amount of height 3 remaining.  Vanya puts the piece of height 3 inside and again there are only 3 centimeters remaining at the end of this second.  Vanya finally puts the pieces of height 2 and 1 inside. At the end of the second the height of potato in the processor is equal to 3.  During this second processor finally smashes all the remaining potato and the process finishes. 

In the second sample, Vanya puts the piece of height 5 inside and waits for 2 seconds while it is completely smashed. Then he repeats the same process for 4 other pieces. The total time is equal to 2·5 = 10 seconds.

In the third sample, Vanya simply puts all the potato inside the processor and waits 2 seconds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string S, the task is to reverse the string using stack.
 
Example 1:
Input: S="GeeksforGeeks"
Output: skeeGrofskeeG
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function reverse() which takes the string S as an input parameter and returns the reversed string.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 ≤ length of the string ≤ 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an easy version of the problem. The actual problems are different, but the easy version is almost a subtask of the hard version. Note that the constraints and the output format are different.

You are given a string $s$ consisting of $n$ lowercase Latin letters.

You have to color all its characters one of the two colors (each character to exactly one color, the same letters can be colored the same or different colors, i.e. you can choose exactly one color for each index in $s$).

After coloring, you can swap any two neighboring characters of the string that are colored different colors. You can perform such an operation arbitrary (possibly, zero) number of times.

The goal is to make the string sorted, i.e. all characters should be in alphabetical order.

Your task is to say if it is possible to color the given string so that after coloring it can become sorted by some sequence of swaps. Note that you have to restore only coloring, not the sequence of swaps.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 200$) — the length of $s$.

The second line of the input contains the string $s$ consisting of exactly $n$ lowercase Latin letters.


-----Output-----

If it is impossible to color the given string so that after coloring it can become sorted by some sequence of swaps, print "NO" (without quotes) in the first line.

Otherwise, print "YES" in the first line and any correct coloring in the second line (the coloring is the string consisting of $n$ characters, the $i$-th character should be '0' if the $i$-th character is colored the first color and '1' otherwise).


-----Examples-----
Input
9
abacbecfd

Output
YES
001010101

Input
8
aaabbcbb

Output
YES
01011011

Input
7
abcdedc

Output
NO

Input
5
abcde

Output
YES
00000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're continuing to enjoy your new piano, as described in Piano Kata, Part 1. You're also continuing the exercise where you start on the very first (leftmost, lowest in pitch) key on the 88-key keyboard, which (as shown below) is the note A, with the little finger on your left hand, then the second key, which is the black key A# ("A sharp"), with your left ring finger, then the third key, B, with your left middle finger, then the fourth key, C, with your left index finger, and then the fifth key, C#, with your left thumb. Then you play the sixth key, D, with your right thumb, and continue on playing the seventh, eighth, ninth, and tenth keys with the other four fingers of your right hand. Then for the eleventh key you go back to your left little finger, and so on. Once you get to the rightmost/highest, 88th, key, C, you start all over again with your left little finger on the first key. 



(If the Codewars Instructions pane resizes the above piano keyboard image to be too small to read the note labels of the black/sharp keys on your screen, click here to open a copy of the image in a new tab or window.)

This time, in addition to counting each key press out loud (not starting again at 1 after 88, but continuing on to 89 and so forth) to try to keep a steady rhythm going and to see how far you can get before messing up, you're also saying the name of each note. You wonder whether this may help you develop perfect pitch in addition to learning to just *know* which note is which, and -- as in Piano Kata, Part 1 -- helping you to learn to move smoothly and with uniform pressure on the keys from each finger to the next and back and forth between hands.

The function you are going to write will explore one of the patterns you're experiencing in your practice: Given the number you stopped on, which note was it? For example, in the description of your piano exercise above, if you stopped at 5, your left thumb would be on the fifth key of the piano, which is C#. Or if you stopped at 92, you would have gone all the way from keys 1 to 88 and then wrapped around, so that you would be on the fourth key, which is C.

Your function will receive an integer between 1 and 10000 (maybe you think that in principle it would be cool to count up to, say, a billion, but considering how many years it would take it is just not possible) and return one of the strings "A", "A#", "B", "C", "C#", "D", "D#", "E", "F", "F#", "G", or "G#" indicating which note you stopped on -- here are a few more examples:
```
1     "A"
12    "G#"
42    "D"
100   "G#"
2017  "F"
```
Have fun!

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

There is an arithmetic progression A with the number of terms N, the first term a, and the tolerance d. Since M statements that rewrite the sequence are given in the following format, find the value of the K item of the sequence A when the sequence A is rewritten M times in the given order.

* The i-th statement is given by the three integers xi, yi, zi. (1 ≤ i ≤ M)

* If xi is 0, the order of values ​​is reversed in the interval from yi item to zi item.

* If xi is 1, each value is incremented by 1 in the interval from yi item to zi item.

* If xi is 2, each value is halved in the interval from yi item to zi item (rounded down to the nearest whole number).

Constraints

* 2 ≤ N ≤ 200000
* 1 ≤ a ≤ 5
* 1 ≤ d ≤ 5
* 1 ≤ M ≤ 200000
* 0 ≤ xi ≤ 2 (1 ≤ i ≤ M)
* 1 ≤ yi ≤ N (1 ≤ i ≤ M)
* 1 ≤ zi ≤ N (1 ≤ i ≤ M)
* yi <zi (1 ≤ i ≤ M)
* 1 ≤ K ≤ N

Input


N
a d
M
x1 y1 z1
x2 y2 z2
...
xM yM zM
K


The first line is given one integer N. On the second line, two integers a and d are given, separated by blanks. On the third line, one integer M is given. Of the M lines from the 4th line, the ith line is given three integers xi, yi, and zi representing the i-th statement, separated by blanks. The last line is given one integer K.

Output

Output the K item when the sequence A is updated M times in the order given by the input.

Examples

Input

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


Output

2


Input

5
1 2
3
1 2 3
2 3 5
0 1 5
1


Output

4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N strings of lowercase English letters: S_1, S_2, \cdots, S_N.
Takahashi wants to make a string that is a palindrome by choosing one or more of these strings - the same string can be chosen more than once - and concatenating them in some order of his choice.
The cost of using the string S_i once is C_i, and the cost of using it multiple times is C_i multiplied by that number of times.
Find the minimum total cost needed to choose strings so that Takahashi can make a palindrome.
If there is no choice of strings in which he can make a palindrome, print -1.

-----Constraints-----
 - 1 \leq N \leq 50
 - 1 \leq |S_i| \leq 20
 - S_i consists of lowercase English letters.
 - 1 \leq C_i \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N
S_1 C_1
S_2 C_2
:
S_N C_N

-----Output-----
Print the minimum total cost needed to choose strings so that Takahashi can make a palindrome, or -1 if there is no such choice.

-----Sample Input-----
3
ba 3
abc 4
cbaa 5

-----Sample Output-----
7

We have ba, abc, and cbaa.
For example, we can use ba once and abc once for a cost of 7, then concatenate them in the order abc, ba to make a palindrome.
Also, we can use abc once and cbaa once for a cost of 9, then concatenate them in the order cbaa, abc to make a palindrome.
We cannot make a palindrome for a cost less than 7, so we should print 7.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a small town the population is `p0 = 1000` at the beginning of a year. The population
regularly increases by `2 percent` per year and moreover `50` new inhabitants per year
come to live in the town. 
How many years does the town need to see its population
greater or equal to `p = 1200` inhabitants?

```
At the end of the first year there will be: 
1000 + 1000 * 0.02 + 50 => 1070 inhabitants

At the end of the 2nd year there will be: 
1070 + 1070 * 0.02 + 50 => 1141 inhabitants (number of inhabitants is an integer)

At the end of the 3rd year there will be:
1141 + 1141 * 0.02 + 50 => 1213

It will need 3 entire years.
```
More generally given parameters:

`p0, percent, aug (inhabitants coming or leaving each year), p (population to surpass)`

the function `nb_year` should return `n` number of entire years needed to
get a population greater or equal to `p`.

aug is an integer, percent a positive or null number, p0 and p are positive integers (> 0)
```
Examples:
nb_year(1500, 5, 100, 5000) -> 15
nb_year(1500000, 2.5, 10000, 2000000) -> 10
```

Note: Don't forget to convert the percent parameter as a percentage in the body of your function: if the parameter percent is 2 you have to convert it to 0.02.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke has decided to construct a string that starts with A and ends with Z, by taking out a substring of a string s (that is, a consecutive part of s).
Find the greatest length of the string Snuke can construct. Here, the test set guarantees that there always exists a substring of s that starts with A and ends with Z.

-----Constraints-----
 - 1 ≦ |s| ≦ 200{,}000
 - s consists of uppercase English letters.
 - There exists a substring of s that starts with A and ends with Z.

-----Input-----
The input is given from Standard Input in the following format:
s

-----Output-----
Print the answer.

-----Sample Input-----
QWERTYASDFZXCV

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

By taking out the seventh through eleventh characters, it is possible to construct ASDFZ, which starts with A and ends with Z.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Each Halloween, the $N$ witches of Sweden all gather high up in the air with their brooms to perform a magical dance. The dance consists of taking one’s broom and rotating clockwise around one of the ends of the broom. Each broom is exactly $1\text { m}$ long, and everyone rotates at the same speed. The $i$’th witch originally starts rotated $r_ i\text { radians}$ clockwise. $0$ radians means that the broom points to the right, i.e. positive $x$-direction; $\pi /2$ radians points in the positive $y$-direction. All the witches are located at the same height in the air, at positions $(x_ i, y_ i)$ for $1 \le i \le N$. Their brooms are always parallel to the $x-y$ plane.

This dance is very beautiful, but has in recent years been plagued by a certain problem. It turns out that nobody had choreographed the dance properly. This caused some of the witches to crash into each other’s brooms. As a result, their brooms would break and they would fall down helplessly, being forced to use their parachutes – can you imagine a greater embarrassment for a witch?

This year, a coalition of witches are tired of their brooms breaking. They have thus produced a choreography beforehand, consisting of the original locations and rotations of the witches’ brooms. Can you check if the dance will cause any brooms to crash into each other?

-----Input-----
The first line of input consists of a single integer $N$ ($1 \le N \le 200000$), the number of witches. The next $N$ lines contains a description of each broom. Each line consists of the real numbers $x_ i, y_ i$ ($-10^{9} \le x_ i \le y_ i 10^{9}$), and the real number $r_ i$ ($0 \le r_ i < 2\pi $), all with at most $20$ digits after the decimal point. The coordinates are measured in meters, and give you the end of the broom that the broom rotates around.

The input will be such that the answer does not change even if the length of the brooms were $1 + 10^{-6}\text { m}$ long.

-----Output-----
Output ok if no witches will crash into each other, and crash if at least one pair of witches will crash.

-----Examples-----
Sample Input:
2
0 0 0
0 1.5 0
Sample Output:
ok

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has an array A of length N such that A_{i} = i.

In one operation, Chef can pick any two elements of the array, delete them from A, and append either their [bitwise XOR] or their [bitwise OR] to A.

Note that after each operation, the length of the array decreases by 1.

Let F be the final number obtained after N-1 operations are made. You are given an integer X, determine if you can get F=X via some sequence of operations.

In case it is possible to get F = X, print the operations too (see the section Output format for more details), otherwise print -1.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line containing two space-separated integers N and X.

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

For each test case, output -1 if it is impossible to get X in the end.
Otherwise print N-1 lines denoting the operations.

On each line, print
- 1\ x\ y if you want replace x and y with x\ OR\ y.
- 2\ x\ y if you want replace x and y with x\ XOR\ y.

Note that x and y are the elements of the array at the time of applying the operation, and if either of them is not present in the array you will receive a WA verdict.

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

$1 ≤ T ≤ 5000$
$2 ≤ N ≤ 2^{15}$
$1 ≤ X ≤ 2^{16} - 1$
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3 2
2 2
4 7

----- Sample Output 1 ------ 
2 1 3
1 2 2
-1
1 1 2
1 3 3
1 3 4

----- explanation 1 ------ 
Test case $1$: The operations are as follows:
- Initially, the array is $A = [1, 2, 3]$
- The first move removes $1$ and $3$ and appends their $XOR$, making the array $A = [2, 2]$
- The second move removes $2$ and $2$ and appends their $OR$, making the array $A = [2]$

Test case $2$: It can be shown that no sequence of operations can achieve $F = 2$ in this case.

Test case $3$: The operations are as follows:
- Initially, the array is $A = [1, 2, 3, 4]$
- After the first move, the array is $A = [3, 4, 3]$
- After the second move, the array is $A = [4, 3]$
- After the third move, the array is $A = [7]$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Being a crewmate in the Among Us game, you will have to solve a task to win against the imposter. 
The task : You are given a certain number of bulbs(Say n) which are initially in OFF position. 
The bulbs are numbered from 1 to n. There will be n current fluctuations in such a way that in the 1st fluctuation all bulbs are toggled, in the 2nd fluctuation every 2nd bulb is toggled, in the 3rd fluctuation every 3rd bulb is toggled and so on.
Your job as a crewmate is to find the number of bulbs which are ON at the end of n fluctuations. But, the imposter has a special power which alerts it when a bulb with a number divisible by 3 is kept ON at the end of n fluctuations. 
So, you will have to switch off the bulbs with numbers divisible by 3 and give the final result to complete the task and win the game.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, an integer $n$. 

-----Output:-----
- For each testcase, output a single integer - the number of bulbs that will remain ON after $n$ fluctuations.

-----Constraints :-----
- $1 \leq T \leq 1000$
- $2 \leq n \leq 10^9$

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

-----Sample Output:-----
1

3

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