vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Recently Luba bought a very interesting book. She knows that it will take t seconds to read the book. Luba wants to finish reading as fast as she can.

But she has some work to do in each of n next days. The number of seconds that Luba has to spend working during i-th day is a_{i}. If some free time remains, she can spend it on reading.

Help Luba to determine the minimum number of day when she finishes reading.

It is guaranteed that the answer doesn't exceed n.

Remember that there are 86400 seconds in a day.


-----Input-----

The first line contains two integers n and t (1 ≤ n ≤ 100, 1 ≤ t ≤ 10^6) — the number of days and the time required to read the book.

The second line contains n integers a_{i} (0 ≤ a_{i} ≤ 86400) — the time Luba has to spend on her work during i-th day.


-----Output-----

Print the minimum day Luba can finish reading the book.

It is guaranteed that answer doesn't exceed n.


-----Examples-----
Input
2 2
86400 86398

Output
2

Input
2 86400
0 86400

Output
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sereja painted n points on the plane, point number i (1 ≤ i ≤ n) has coordinates (i, 0). Then Sereja marked each point with a small or large English letter. Sereja don't like letter "x", so he didn't use it to mark points. Sereja thinks that the points are marked beautifully if the following conditions holds:

  * all points can be divided into pairs so that each point will belong to exactly one pair; 
  * in each pair the point with the lesser abscissa will be marked with a small English letter and the point with the larger abscissa will be marked with the same large English letter; 
  * if we built a square on each pair, the pair's points will be the square's opposite points and the segment between them will be the square's diagonal, then among the resulting squares there won't be any intersecting or touching ones. 



Little Petya erased some small and all large letters marking the points. Now Sereja wonders how many ways are there to return the removed letters so that the points were marked beautifully.

Input

The first line contains integer n the number of points (1 ≤ n ≤ 105). The second line contains a sequence consisting of n small English letters and question marks — the sequence of letters, that mark points, in order of increasing x-coordinate of points. Question marks denote the points without letters (Petya erased them). It is guaranteed that the input string doesn't contain letter "x".

Output

In a single line print the answer to the problem modulo 4294967296. If there is no way to return the removed letters, print number 0.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

4
a???


Output

50


Input

4
abc?


Output

0


Input

6
abc???


Output

1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a pointer to the root of a binary search tree and values to be inserted into the tree. Insert the values into their appropriate position in the binary search tree and return the root of the updated binary tree.
You just have to complete the function.

Input Format

You are given a function,

Node * insert (Node * root ,int data) {

}

Constraints

No. of nodes in the  tree $\leq$ 500

Output Format

Return the root of the binary search tree after inserting the value into the tree.

Sample Input
        4
       / \
      2   7
     / \
    1   3

The value to be inserted is 6.

Sample Output
         4
       /   \
      2     7
     / \   /
    1   3 6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We all know the town Radiator Springs, connected to California by direct road (Route no. 66). After a commendable performance by Lighting McQueen 
at the Piston Cup, the town of Radiator Springs became famous. In order to improve the traffic capacity of the road, the town's judge 
and doctor, Doc Hudson ordered to place on traffic sign, thus limiting the maximum speed. The traffic sign in the town of Radiator Springs 
seems to be a bit odd. The reason being, they only limit the speed where the traffic signals are placed and just after passing the sign the 
cars are allowed to drive at any speed.

It is given that the cars of Radiator Springs has an average accerleration/deceleration of x km/h^2, and has a maximum speed of 
y km/h. The road has the length of L km, and the speed sign, limiting the speed to w km/h, is placed d km (1 ≤ d ≤ L) away from the Radiator Springs.
You have to find the minimum time that an average Radiator Spring car will need to get from the California, if the car drives at the optimal speed.

Note : The car has a zero speed at the beginning of the journey.

Input format

The first line of the input file contains two integer numbers x and y (1 ≤ x, y ≤ 10000).
The second line contains three integer numbers L, d and w (2  ≤ L ≤ 10000; 1 ≤ d < L; 1 ≤ w ≤ 10000).

Output format

Print the answer with nine digits after the decimal point.

Partial Scoring

This problem has 20 test input files,each of them having score of 5. It means even if 10 input are passed, you will get score as 50 and solution will be marked as accepted. But If the total time limit or memory limit exceeds, then the submission is marked unaccepted even if few testcases might have passed.

SAMPLE INPUT
1 1
2 1 3

SAMPLE OUTPUT
2.500000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arkady and his friends love playing checkers on an $n \times n$ field. The rows and the columns of the field are enumerated from $1$ to $n$.

The friends have recently won a championship, so Arkady wants to please them with some candies. Remembering an old parable (but not its moral), Arkady wants to give to his friends one set of candies per each cell of the field: the set of candies for cell $(i, j)$ will have exactly $(i^2 + j^2)$ candies of unique type.

There are $m$ friends who deserve the present. How many of these $n \times n$ sets of candies can be split equally into $m$ parts without cutting a candy into pieces? Note that each set has to be split independently since the types of candies in different sets are different.


-----Input-----

The only line contains two integers $n$ and $m$ ($1 \le n \le 10^9$, $1 \le m \le 1000$) — the size of the field and the number of parts to split the sets into.


-----Output-----

Print a single integer — the number of sets that can be split equally.


-----Examples-----
Input
3 3

Output
1

Input
6 5

Output
13

Input
1000000000 1

Output
1000000000000000000



-----Note-----

In the first example, only the set for cell $(3, 3)$ can be split equally ($3^2 + 3^2 = 18$, which is divisible by $m=3$).

In the second example, the sets for the following cells can be divided equally:   $(1, 2)$ and $(2, 1)$, since $1^2 + 2^2 = 5$, which is divisible by $5$;  $(1, 3)$ and $(3, 1)$;  $(2, 4)$ and $(4, 2)$;  $(2, 6)$ and $(6, 2)$;  $(3, 4)$ and $(4, 3)$;  $(3, 6)$ and $(6, 3)$;  $(5, 5)$. 

In the third example, sets in all cells can be divided equally, since $m = 1$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya was late for the lesson too. The teacher gave him an additional task. For some array *a* Petya should find the number of different ways to select non-empty subset of elements from it in such a way that their product is equal to a square of some integer.

Two ways are considered different if sets of indexes of elements chosen by these ways are different.

Since the answer can be very large, you should find the answer modulo 109<=+<=7.

Input Specification:
First line contains one integer *n* (1<=≤<=*n*<=≤<=105) — the number of elements in the array.

Second line contains *n* integers *a**i* (1<=≤<=*a**i*<=≤<=70) — the elements of the array.

Output Specification:
Print one integer — the number of different ways to choose some elements so that their product is a square of a certain integer modulo 109<=+<=7.

Demo Input:
['4\n1 1 1 1\n', '4\n2 2 2 2\n', '5\n1 2 4 5 8\n']

Demo Output:
['15\n', '7\n', '7\n']

Note:
In first sample product of elements chosen by any way is 1 and 1 = 1<sup class="upper-index">2</sup>. So the answer is 2<sup class="upper-index">4</sup> - 1 = 15.

In second sample there are six different ways to choose elements so that their product is 4, and only one way so that their product is 16. So the answer is 6 + 1 = 7.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bholu the Pandit on this New Year wanted to divide his Cuboidal Packaging block into cubes.
But he loves uniformity so he asks you to divide it such a way that all the cubes are of same size and volume of individual cube is as large as possible.

Note: He will utilize whole volume i.e volume of cuboid before dividing is same as sum of volume of all the cubes.

Input
The first input line contains an integer T, the number of testcases. 
Each testcase consist of single line which consist of 3 space separated integers a, b & c representing length, breadth and height of the Cuboidal block.

Output
For each testcase you need to output 2 space separated integers, the length of side of the cube and the number of cubes which could be formed out of this cuboidal packaging block.
As the number of cubes which could be made could be a large number so just output the answer modulus 10^9+7 (1000000007).

Constraints
1 ≤ T ≤ 1000
1 ≤ a,b,c ≤ 10^9

SAMPLE INPUT
2
2 4 6
1 2 3

SAMPLE OUTPUT
2 6
1 6

Explanation

In the 1st testcase a=2, b=4 & c=6.
So length of the side of the cube would be 2 and the number of cubes which would be formed would be 6.
In the 2nd testcase a=1, b=2 & c=3.
So length of the side of the cube would be 1 and the number of cubes which would be formed would be 6.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Arthur and Alexander are number busters. Today they've got a competition. 

Arthur took a group of four integers *a*,<=*b*,<=*w*,<=*x* (0<=≤<=*b*<=&lt;<=*w*,<=0<=&lt;<=*x*<=&lt;<=*w*) and Alexander took integer *с*. Arthur and Alexander use distinct approaches to number bustings. Alexander is just a regular guy. Each second, he subtracts one from his number. In other words, he performs the assignment: *c*<==<=*c*<=-<=1. Arthur is a sophisticated guy. Each second Arthur performs a complex operation, described as follows: if *b*<=≥<=*x*, perform the assignment *b*<==<=*b*<=-<=*x*, if *b*<=&lt;<=*x*, then perform two consecutive assignments *a*<==<=*a*<=-<=1; *b*<==<=*w*<=-<=(*x*<=-<=*b*).

You've got numbers *a*,<=*b*,<=*w*,<=*x*,<=*c*. Determine when Alexander gets ahead of Arthur if both guys start performing the operations at the same time. Assume that Alexander got ahead of Arthur if *c*<=≤<=*a*.

Input Specification:
The first line contains integers *a*,<=*b*,<=*w*,<=*x*,<=*c* (1<=≤<=*a*<=≤<=2·109,<=1<=≤<=*w*<=≤<=1000,<=0<=≤<=*b*<=&lt;<=*w*,<=0<=&lt;<=*x*<=&lt;<=*w*,<=1<=≤<=*c*<=≤<=2·109).

Output Specification:
Print a single integer — the minimum time in seconds Alexander needs to get ahead of Arthur. You can prove that the described situation always occurs within the problem's limits.

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

Demo Output:
['2\n', '4\n', '13\n', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Paul hates palindromes. He assumes that string s is tolerable if each its character is one of the first p letters of the English alphabet and s doesn't contain any palindrome contiguous substring of length 2 or more.

Paul has found a tolerable string s of length n. Help him find the lexicographically next tolerable string of the same length or else state that such string does not exist.


-----Input-----

The first line contains two space-separated integers: n and p (1 ≤ n ≤ 1000; 1 ≤ p ≤ 26). The second line contains string s, consisting of n small English letters. It is guaranteed that the string is tolerable (according to the above definition).


-----Output-----

If the lexicographically next tolerable string of the same length exists, print it. Otherwise, print "NO" (without the quotes).


-----Examples-----
Input
3 3
cba

Output
NO

Input
3 4
cba

Output
cbd

Input
4 4
abcd

Output
abda



-----Note-----

String s is lexicographically larger (or simply larger) than string t with the same length, if there is number i, such that s_1 = t_1, ..., s_{i} = t_{i}, s_{i} + 1 > t_{i} + 1.

The lexicographically next tolerable string is the lexicographically minimum tolerable string which is larger than the given one.

A palindrome is a string that reads the same forward or reversed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Right now she actually isn't. But she will be, if you don't solve this problem.

You are given integers n, k, A and B. There is a number x, which is initially equal to n. You are allowed to perform two types of operations:   Subtract 1 from x. This operation costs you A coins.  Divide x by k. Can be performed only if x is divisible by k. This operation costs you B coins.  What is the minimum amount of coins you have to pay to make x equal to 1?


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 2·10^9).

The second line contains a single integer k (1 ≤ k ≤ 2·10^9).

The third line contains a single integer A (1 ≤ A ≤ 2·10^9).

The fourth line contains a single integer B (1 ≤ B ≤ 2·10^9).


-----Output-----

Output a single integer — the minimum amount of coins you have to pay to make x equal to 1.


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

Output
6

Input
5
5
2
20

Output
8

Input
19
3
4
2

Output
12



-----Note-----

In the first testcase, the optimal strategy is as follows:   Subtract 1 from x (9 → 8) paying 3 coins.  Divide x by 2 (8 → 4) paying 1 coin.  Divide x by 2 (4 → 2) paying 1 coin.  Divide x by 2 (2 → 1) paying 1 coin. 

The total cost is 6 coins.

In the second test case the optimal strategy is to subtract 1 from x 4 times paying 8 coins in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n cows playing poker at a table. For the current betting phase, each player's status is either "ALLIN", "IN", or "FOLDED", and does not change throughout the phase. To increase the suspense, a player whose current status is not "FOLDED" may show his/her hand to the table. However, so as not to affect any betting decisions, he/she may only do so if all other players have a status of either "ALLIN" or "FOLDED". The player's own status may be either "ALLIN" or "IN".

Find the number of cows that can currently show their hands without affecting any betting decisions.


-----Input-----

The first line contains a single integer, n (2 ≤ n ≤ 2·10^5). The second line contains n characters, each either "A", "I", or "F". The i-th character is "A" if the i-th player's status is "ALLIN", "I" if the i-th player's status is "IN", or "F" if the i-th player's status is "FOLDED".


-----Output-----

The first line should contain a single integer denoting the number of players that can currently show their hands.


-----Examples-----
Input
6
AFFAAA

Output
4

Input
3
AFI

Output
1



-----Note-----

In the first sample, cows 1, 4, 5, and 6 can show their hands. In the second sample, only cow 3 can show her hand.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a binary heap implementation of Priority Queue. Extract the maximum element from the queue i.e. remove it from the Queue and return it's value. 
 
Example 1:
Input: 4 2 8 16 24 2 6 5
Output: 24
Priority Queue after extracting maximum: 16 8 6 5 2 2 4
Example 2:
Input: 64 12 8 48 5
Output: 64
Priority Queue after extracting maximum: 48 12 8 5
 
Your Task:
Complete the function extractMax() which extracts the maximum element, i.e. remove it from the Queue and return it's value.
 
Expected Time Complexity: O(logN)
Expected Space Complexity: O(N)
 
Constraints:
1<=N<=500

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have an integer sequence A of length N, where A_1 = X, A_{i+1} = A_i + D (1 \leq  i < N ) holds.
Takahashi will take some (possibly all or none) of the elements in this sequence, and Aoki will take all of the others.
Let S and T be the sum of the numbers taken by Takahashi and Aoki, respectively. How many possible values of S - T are there?

-----Constraints-----
 - -10^8 \leq X, D \leq 10^8
 - 1 \leq N \leq 2 \times 10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N X D

-----Output-----
Print the number of possible values of S - T.

-----Sample Input-----
3 4 2

-----Sample Output-----
8

A is (4, 6, 8).
There are eight ways for (Takahashi, Aoki) to take the elements: ((), (4, 6, 8)), ((4), (6, 8)), ((6), (4, 8)), ((8), (4, 6))), ((4, 6), (8))), ((4, 8), (6))), ((6, 8), (4))), and ((4, 6, 8), ()).
The values of S - T in these ways are -18, -10, -6, -2, 2, 6, 10, and 18, respectively, so there are eight possible values of S - T.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your boss decided to save money by purchasing some cut-rate optical character recognition software for scanning in the text of old novels to your database. At first it seems to capture words okay, but you quickly notice that it throws in a lot of numbers at random places in the text. For example:

```python
string_clean('! !') == '! !'
string_clean('123456789') == ''
string_clean('This looks5 grea8t!') == 'This looks great!'

```

Your harried co-workers are looking to you for a solution to take this garbled text and remove all of the numbers. Your program will take in a string and clean out all numeric characters, and return a string with spacing and special characters `~#$%^&!@*():;"'.,?` all intact.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an undirected tree consisting of $n$ vertices. An undirected tree is a connected undirected graph with $n - 1$ edges.

Your task is to add the minimum number of edges in such a way that the length of the shortest path from the vertex $1$ to any other vertex is at most $2$. Note that you are not allowed to add loops and multiple edges.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

The following $n - 1$ lines contain edges: edge $i$ is given as a pair of vertices $u_i, v_i$ ($1 \le u_i, v_i \le n$). It is guaranteed that the given edges form a tree. It is guaranteed that there are no loops and multiple edges in the given edges.


-----Output-----

Print a single integer — the minimum number of edges you have to add in order to make the shortest distance from the vertex $1$ to any other vertex at most $2$. Note that you are not allowed to add loops and multiple edges.


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

Output
2

Input
7
1 2
1 3
2 4
2 5
3 6
1 7

Output
0

Input
7
1 2
2 3
3 4
3 5
3 6
3 7

Output
1



-----Note-----

The tree corresponding to the first example: [Image] The answer is $2$, some of the possible answers are the following: $[(1, 5), (1, 6)]$, $[(1, 4), (1, 7)]$, $[(1, 6), (1, 7)]$.

The tree corresponding to the second example: [Image] The answer is $0$.

The tree corresponding to the third example: [Image] The answer is $1$, only one possible way to reach it is to add the edge $(1, 3)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
DZY has a hash table with p buckets, numbered from 0 to p - 1. He wants to insert n numbers, in the order they are given, into the hash table. For the i-th number x_{i}, DZY will put it into the bucket numbered h(x_{i}), where h(x) is the hash function. In this problem we will assume, that h(x) = x mod p. Operation a mod b denotes taking a remainder after division a by b.

However, each bucket can contain no more than one element. If DZY wants to insert an number into a bucket which is already filled, we say a "conflict" happens. Suppose the first conflict happens right after the i-th insertion, you should output i. If no conflict happens, just output -1.


-----Input-----

The first line contains two integers, p and n (2 ≤ p, n ≤ 300). Then n lines follow. The i-th of them contains an integer x_{i} (0 ≤ x_{i} ≤ 10^9).


-----Output-----

Output a single integer — the answer to the problem.


-----Examples-----
Input
10 5
0
21
53
41
53

Output
4

Input
5 5
0
1
2
3
4

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to ___find the next higher number (int) with same '1'- Bits___.

I.e. as much `1` bits as before and output next higher than input. Input is always an int in between 1 and 1<<30 (inclusive). No bad cases or special tricks... 

### Some easy examples:

```
Input: 129  => Output: 130 (10000001 => 10000010)
Input: 127 => Output: 191 (01111111 => 10111111)
Input: 1 => Output: 2 (01 => 10)
Input: 323423 => Output: 323439 (1001110111101011111 => 1001110111101101111)
```

First some static tests, later on many random tests too;-)!

### Hope you have fun! :-)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp recently became an employee of the company "Double Permutation Inc." Now he is a fan of permutations and is looking for them everywhere!

A permutation in this problem is a sequence of integers p_1, p_2, ..., p_k such that every integer from 1 to k occurs exactly once in it. For example, the following sequences are permutations of [3, 1, 4, 2], [1] and [6, 1, 2, 3, 5, 4]. The following sequences are not permutations: [0, 1], [1, 2, 2], [1, 2, 4] and [2, 3].

In the lobby of the company's headquarter statistics on visits to the company's website for the last n days are published — the sequence a_1, a_2, ..., a_n. Polycarp wants to color all the elements of this sequence in one of three colors (red, green or blue) so that:

  * all red numbers, being written out of a_1, a_2, ..., a_n from left to right (that is, without changing their relative order), must form some permutation (let's call it P); 
  * all green numbers, being written out of a_1, a_2, ..., a_n from left to right (that is, without changing their relative order), must form the same permutation P; 
  * among blue numbers there should not be elements that are equal to some element of the permutation P. 



Help Polycarp to color all n numbers so that the total number of red and green elements is maximum.

Input

The first line contains an integer n (1 ≤ n ≤ 2⋅10^5) — the length of the sequence a. The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 2⋅10^5).

Output

Print a string s of length n such that:

  * s_i='R', if the element a_i must be colored in red; 
  * s_i='G', if the element a_i must be colored in green; 
  * s_i='B', if the element a_i must be colored in blue. 



The string s should maximize the total number of red and green elements when fulfilling the requirements from the main part of the problem statement. If there are several optimal answers, print any of them.

Examples

Input


5
1 2 3 2 1


Output


RBBBG


Input


3
1 1 1


Output


BBB


Input


10
3 3 2 2 5 4 1 5 4 1


Output


RGRGRRRGGG


Input


10
3 9 3 1 2 1 2 4 4 4


Output


RBGRRGGBBB

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