vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an array $a_1, a_2, \dots, a_n$. All $a_i$ are pairwise distinct.

Let's define function $f(l, r)$ as follows:   let's define array $b_1, b_2, \dots, b_{r - l + 1}$, where $b_i = a_{l - 1 + i}$;  sort array $b$ in increasing order;  result of the function $f(l, r)$ is $\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot i}$. 

Calculate $\left(\sum\limits_{1 \le l \le r \le n}{f(l, r)}\right) \mod (10^9+7)$, i.e. total sum of $f$ for all subsegments of $a$ modulo $10^9+7$.


-----Input-----

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

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$, $a_i \neq a_j$ for $i \neq j$) — array $a$.


-----Output-----

Print one integer — the total sum of $f$ for all subsegments of $a$ modulo $10^9+7$


-----Examples-----
Input
4
5 2 4 7

Output
167

Input
3
123456789 214365879 987654321

Output
582491518



-----Note-----

Description of the first example:   $f(1, 1) = 5 \cdot 1 = 5$;  $f(1, 2) = 2 \cdot 1 + 5 \cdot 2 = 12$;  $f(1, 3) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 = 25$;  $f(1, 4) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 + 7 \cdot 4 = 53$;  $f(2, 2) = 2 \cdot 1 = 2$;  $f(2, 3) = 2 \cdot 1 + 4 \cdot 2 = 10$;  $f(2, 4) = 2 \cdot 1 + 4 \cdot 2 + 7 \cdot 3 = 31$;  $f(3, 3) = 4 \cdot 1 = 4$;  $f(3, 4) = 4 \cdot 1 + 7 \cdot 2 = 18$;  $f(4, 4) = 7 \cdot 1 = 7$;

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Being a space captain can be a dangerous endeavour, especially when conducting missions in Borg space. Today your captain has been tasked with beaming aboard a Borg spaceship to see if he can discover anything useful. The Borg ship consist of rooms connected with passages of equal length, and with no more than one direct passage between any two rooms. It is possible to find a path from any room to any other. 

On the Borg ship there is also a sentry, placed there by the Borg eons ago. This sentry operates according to a rather unsophisticated algorithm, namely walking at random. This gives the sentry one advantage, however: You will never know where it is! More precisely, once every minute, the sentry chooses one of the neighbouring rooms with uniform probability, and walks quickly to this room. Your captain will also be spending exactly one minute in each room, and to minimise the chances that he will meet the sentry, you time his movement such that he and the sentry move at exactly the same time. Thus he will be caught by the sentry if and only if the two of them move into the same room at the same time, or if they try to swap rooms.

Star Fleet has issued as a direct order the rooms your captain is to visit, and in the exact order. These rooms form a walk on the Borg ship, where each room may be visited several times. Star Fleet has also provided you with a map of the ship. The captain will be beamed down to the first room of the walk, and will be beamed back up from the last room. He risks capture in both these rooms.

Now the captain starts wondering about the chances of success on this mission, hoping them to be very low indeed. After all, that makes it all the more interesting! Getting curious yourself, you decide you want to figure this out. Unfortunately the ship’s android is experiencing problems with his new emotion chip, and thus the task falls on you to compute the captain’s chances of success on this dangerous mission!

-----Input-----
One line with $2 \leq N \leq 500$ – the number of nodes.

One line with $1 \leq L \leq 500$ – the number of rooms the captain must visit.

One line with $L$ integers describing the captain’s walk, i.e., they give the exact walk the captain must perform.

$N$ lines beginning with an integer $n_ i$ – the number of neighbours of node $i$ – followed by $n_ i$ integers – the neighbours of node $i$, $0$-indexed.

-----Output-----
The chance the captain will be able to complete his mission without being discovered by the Borg sentry. The answer should be correct within an absolute or relative error of $10^{-6}$

-----Examples-----
Sample Input 1:
3
1
0
2 1 2
1 0
1 0
Sample Output 1:
0.5

Sample Input 2:
8
6
1 0 2 3 0 1
7 1 2 3 4 5 6 7
1 0
2 0 3
2 0 2
1 0
1 0
1 0
1 0
Sample Output 2:
0.0446429

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given the integer $n$ — the number of available blocks. You must use all blocks to build a pedestal.

The pedestal consists of $3$ platforms for $2$-nd, $1$-st and $3$-rd places respectively. The platform for the $1$-st place must be strictly higher than for the $2$-nd place, and the platform for the $2$-nd place must be strictly higher than for the $3$-rd place. Also, the height of each platform must be greater than zero (that is, each platform must contain at least one block).

Example pedestal of $n=11$ blocks: second place height equals $4$ blocks, first place height equals $5$ blocks, third place height equals $2$ blocks.

Among all possible pedestals of $n$ blocks, deduce one such that the platform height for the $1$-st place minimum as possible. If there are several of them, output any of them.


-----Input-----

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

Each test case contains a single integer $n$ ($6 \le n \le 10^5$) — the total number of blocks for the pedestal. All $n$ blocks must be used.

It is guaranteed that the sum of $n$ values over all test cases does not exceed $10^6$.


-----Output-----

For each test case, output $3$ numbers $h_2, h_1, h_3$ — the platform heights for $2$-nd, $1$-st and $3$-rd places on a pedestal consisting of $n$ blocks ($h_1+h_2+h_3=n$, $0 < h_3 < h_2 < h_1$).

Among all possible pedestals, output the one for which the value of $h_1$ minimal. If there are several of them, output any of them.


-----Examples-----

Input
6
11
6
10
100000
7
8
Output
4 5 2
2 3 1
4 5 1
33334 33335 33331
2 4 1
3 4 1


-----Note-----

In the first test case we can not get the height of the platform for the first place less than $5$, because if the height of the platform for the first place is not more than $4$, then we can use at most $4 + 3 + 2 = 9$ blocks. And we should use $11 = 4 + 5 + 2$ blocks. Therefore, the answer 4 5 2 fits.

In the second set, the only suitable answer is: 2 3 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string, say S, print it in reverse manner eliminating the repeated characters and spaces.
Example 1:
Input: S = "GEEKS FOR GEEKS"
Output: "SKEGROF"
Example 2:
Input: S = "I AM AWESOME"
Output: "EMOSWAI"
Your Task:
You don't need to read input or print anything. Your task is to complete the function reverseString() which takes a string S as input parameter and returns a modified string. 
Expected Time Complexity: O(|S|), where |S| denotes length of string.
Expected Auxiliary Space: O(1).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
E869120 found a chest which is likely to contain treasure.

However, the chest is locked. In order to open it, he needs to enter a string S consisting of lowercase English letters.

He also found a string S', which turns out to be the string S with some of its letters (possibly all or none) replaced with ?.  
One more thing he found is a sheet of paper with the following facts written on it:  
 - Condition 1: The string S contains a string T as a contiguous substring.
 - Condition 2: S is the lexicographically smallest string among the ones that satisfy Condition 1.
Print the string S.

If such a string does not exist, print UNRESTORABLE.  

-----Constraints-----
 - 1 \leq |S'|, |T| \leq 50
 - S' consists of lowercase English letters and ?.
 - T consists of lowercase English letters.

-----Input-----
Input is given from Standard Input in the following format:
S
T'

-----Output-----
Print the string S.

If such a string does not exist, print UNRESTORABLE instead.  

-----Sample Input-----
?tc????
coder

-----Sample Output-----
atcoder

There are 26 strings that satisfy Condition 1: atcoder, btcoder, ctcoder,..., ztcoder.
Among them, the lexicographically smallest is atcoder, so we can say S = atcoder.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Masha is fond of cacti. When she was a little girl, she decided to plant a tree. Now Masha wants to make a nice cactus out of her tree.

Recall that tree is a connected undirected graph that has no cycles. Cactus is a connected undirected graph such that each vertex belongs to at most one cycle.

Masha has some additional edges that she can add to a tree. For each edge she knows which vertices it would connect and the beauty of this edge. Masha can add some of these edges to the graph if the resulting graph is a cactus. Beauty of the resulting cactus is sum of beauties of all added edges. 

Help Masha find out what maximum beauty of the resulting cactus she can achieve.

Input

The first line of the input data contains two integers n and m — the number of vertices in a tree, and the number of additional edges available (3 ≤ n ≤ 2·105; 0 ≤ m ≤ 2·105).

Let us describe Masha's tree. It has a root at vertex 1. The second line contains n - 1 integers: p2, p3, ..., pn, here pi — is the parent of a vertex i — the first vertex on a path from the vertex i to the root of the tree (1 ≤ pi < i).

The following m lines contain three integers ui, vi and ci — pairs of vertices to be connected by the additional edges that Masha can add to the tree and beauty of edge (1 ≤ ui, vi ≤ n; ui ≠ vi; 1 ≤ ci ≤ 104).

It is guaranteed that no additional edge coincides with the edge of the tree.

Output

Output one integer — the maximum beauty of a cactus Masha can achieve.

Example

Input

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


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have the integer `9457`. 

We distribute its digits in two buckets having the following possible distributions (we put the generated numbers as strings and we add the corresponding formed integers for each partition):
```
- one bucket with one digit and the other with three digits 
[['9'], ['4','5','7']] --> ['9','457'] --> 9 + 457 = 466
[['9','5','7'], ['4']] --> ['957','4'] --> 957 + 4 = 961
[['9','4','7'], ['5']] --> ['947','5'] --> 947 + 5 = 952
[['9','4','5'], ['7']] --> ['945','7'] --> 945 + 7 = 952

- two buckets with 2 digits each:
[['9','4'], ['5','7']] --> ['94','57'] --> 94 + 57 = 151
[['9','5'], ['4','7']] --> ['95','47'] --> 95 + 47 = 142
[['9','7'], ['4','5']] --> ['97','45'] --> 97 + 45 = 142
```

Now we distribute the digits of that integer in three buckets, and we do the same presentation as above:
```
one bucket of two digits and two buckets with one digit each:
[['9'], ['4'], ['5','7']] --> ['9','4','57'] --> 9 + 4 + 57 = 70
[['9','4'], ['5'], ['7']] --> ['94','5','7'] --> 94 + 5 + 7 = 106
[['9'], ['4', '5'], ['7']] --> ['9','45','7'] --> 9 + 45 + 7 = 61
[['9'], ['5'], ['4','7']] --> ['9','5','47'] --> 9 + 5 + 47 = 61
[['9','5'], ['4'], ['7']] --> ['95','4','7'] --> 95 + 4 + 7 = 106
[['9','7'], ['4'], ['5']] --> ['97','4','5'] --> 97 + 4 + 5 = 106
```
Finally we distribute the digits in the maximum possible amount of buckets for this integer, four buckets, with an unique distribution:
```
One digit in each bucket.
[['9'], ['4'], ['5'], ['7']] --> ['9','4','5','7'] --> 9 + 4 + 5 + 7 = 25
```
In the distribution we can observe the following aspects:

- the order of the buckets does not matter

- the order of the digits in each bucket matters; the available digits have the same order than in the original number.

- the amount of buckets varies from two up to the amount of digits

The function, `f =` `bucket_digit_distributions_total_sum`, gives for each integer, the result of the big sum of the total addition of generated numbers for each distribution of digits.
```python
bucket_digit_distributions_total_sum(9457) === 4301 # 466 + 961 + 952 + 952 + 151 + 142 + 142 + 70 + 106 + 61 + 61 + 106 + 106 + 25 = 4301
```
It is interesting to see the value of this function for a number that has one or more zeroes as digits, for example:
```python
bucket_digit_distributions_total_sum(10001) === 5466
```
Given an integer `n`, with its corresponding value of the above function, `f(n)`, and another integer `z`, find the closest and higher integer to n, `nf`, such `f(nf) > f(n) + z`.

Example:
```python
find(10001,100) === 10003
find(30000, 1000) === 30046
``` 
Features of the random tests:
```
100 <= n <= 1500000
50 <= z <= 6000
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pankaj is a loiter person, 
at once his mentor who is a great mathematician call him for some urgent work 
but due to his bad habit Pankaj forgot about it
for that his mentor was very angry and want to punish him
so he gives a series of real numbers (each number has value less than one) to Pankaj
for calculate the minimum value of P and Q if possible,where (P/Q==NUMBER)  .
you are Pankaj's friend and want to help him by calculating values of P and Q
but you have not sufficient time to do this manually so you decided to make a program for that.

"..." will be used to denote the infinite recurring sequence of any digits, if there is no one repetition in given string till "..." then there will be a non recurring sequence up-to infinite.

note: in case of any conflict in recurrence we will take recurrence of maximum length.
if you do not know about rational number then go through this link enter link description here

input:

First line contains total numbers t which will be followed by t strings each string has a number.

output:

if possible to calculate print the minimum Value of P and Q.

constraints:

1 ≤ t=<100

3 ≤ string length(input) ≤ 16

SAMPLE INPUT
3
0.333...
0.4345...
0.3

SAMPLE OUTPUT
P=1 Q=3
P=3 Q=10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A football league of N teams is taking place, where each team plays other teams once in [single round robin] fashion. A team gets 3 points for winning a game and 0 for losing (assume that no games end in a draw/tie). What is the maximum possible difference of points between the winning team and the second-placed team?

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

- The first line of input will contain a single integer T, denoting the number of test cases. Then the test cases follow.
- Each test case consists of a single line of input, containing a single integer N.

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

For each test case, output in a single line the maximum difference of points between first and second place.

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
4
2
3
4
9
----- Sample Output 1 ------ 
3
3
6
12
----- explanation 1 ------ 
Test case $1$: There will only be one match played between the two teams, therefore one team wins by $3$ points.

Test case $2$: Let the three teams be A, B, C. If team A wins both the games against team B and team C, then team A will win by $3$ points since one of team B and team C will win the game between them.

Test case $3$: Let the four teams be A, B, C, D. One possibility is for A to win all its games, and then B beats C, C beats D, D beats B. This way, the winner has $9$ points and second place has $3$ points, making a difference of $6$.

Test case $4$: It can be shown that it's not possible to achieve a difference higher than $12$ when $9$ teams play. One way of achieving this is for the winner to score $24$ points and second place to score $12$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a string S. Each character in S is either a digit (0, ..., 9) or ?.
Among the integers obtained by replacing each occurrence of ? with a digit, how many have a remainder of 5 when divided by 13? An integer may begin with 0.
Since the answer can be enormous, print the count modulo 10^9+7.

-----Constraints-----
 - S is a string consisting of digits (0, ..., 9) and ?.
 - 1 \leq |S| \leq 10^5

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print the number of integers satisfying the condition, modulo 10^9+7.

-----Sample Input-----
??2??5

-----Sample Output-----
768

For example, 482305, 002865, and 972665 satisfy the condition.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a lowercase English letter c, determine whether it is a vowel. Here, there are five vowels in the English alphabet: a, e, i, o and u.

-----Constraints-----
 - c is a lowercase English letter.

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

-----Output-----
If c is a vowel, print vowel. Otherwise, print consonant.

-----Sample Input-----
a

-----Sample Output-----
vowel

Since a is a vowel, print vowel.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day Kefa the parrot was walking down the street as he was on the way home from the restaurant when he saw something glittering by the road. As he came nearer he understood that it was a watch. He decided to take it to the pawnbroker to earn some money. 

The pawnbroker said that each watch contains a serial number represented by a string of digits from 0 to 9, and the more quality checks this number passes, the higher is the value of the watch. The check is defined by three positive integers l, r and d. The watches pass a check if a substring of the serial number from l to r has period d. Sometimes the pawnbroker gets distracted and Kefa changes in some substring of the serial number all digits to c in order to increase profit from the watch. 

The seller has a lot of things to do to begin with and with Kefa messing about, he gave you a task: to write a program that determines the value of the watch.

Let us remind you that number x is called a period of string s (1 ≤ x ≤ |s|), if si = si + x for all i from 1 to |s| - x.

Input

The first line of the input contains three positive integers n, m and k (1 ≤ n ≤ 105, 1 ≤ m + k ≤ 105) — the length of the serial number, the number of change made by Kefa and the number of quality checks.

The second line contains a serial number consisting of n digits.

Then m + k lines follow, containing either checks or changes. 

The changes are given as 1 l r c (1 ≤ l ≤ r ≤ n, 0 ≤ c ≤ 9). That means that Kefa changed all the digits from the l-th to the r-th to be c. 

The checks are given as 2 l r d (1 ≤ l ≤ r ≤ n, 1 ≤ d ≤ r - l + 1).

Output

For each check on a single line print "YES" if the watch passed it, otherwise print "NO".

Examples

Input

3 1 2
112
2 2 3 1
1 1 3 8
2 1 2 1


Output

NO
YES


Input

6 2 3
334934
2 2 5 2
1 4 4 3
2 1 6 3
1 2 3 8
2 3 6 1


Output

NO
YES
NO

Note

In the first sample test two checks will be made. In the first one substring "12" is checked on whether or not it has period 1, so the answer is "NO". In the second one substring "88", is checked on whether or not it has period 1, and it has this period, so the answer is "YES".

In the second statement test three checks will be made. The first check processes substring "3493", which doesn't have period 2. Before the second check the string looks as "334334", so the answer to it is "YES". And finally, the third check processes substring "8334", which does not have period 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rebel spy Heidi has just obtained the plans for the Death Star from the Empire and, now on her way to safety, she is trying to break the encryption of the plans (of course they are encrypted – the Empire may be evil, but it is not stupid!). The encryption has several levels of security, and here is how the first one looks.

Heidi is presented with a screen that shows her a sequence of integers A and a positive integer p. She knows that the encryption code is a single number S, which is defined as follows:

Define the score of X to be the sum of the elements of X modulo p.

Heidi is given a sequence A that consists of N integers, and also given an integer p. She needs to split A into 2 parts such that:   Each part contains at least 1 element of A, and each part consists of contiguous elements of A.  The two parts do not overlap.  The total sum S of the scores of those two parts is maximized. This is the encryption code. 

Output the sum S, which is the encryption code.


-----Input-----

The first line of the input contains two space-separated integer N and p (2 ≤ N ≤ 100 000, 2 ≤ p ≤ 10 000) – the number of elements in A, and the modulo for computing scores, respectively.

The second line contains N space-separated integers which are the elements of A. Each integer is from the interval [1, 1 000 000].


-----Output-----

Output the number S as described in the problem statement.


-----Examples-----
Input
4 10
3 4 7 2

Output
16

Input
10 12
16 3 24 13 9 8 7 5 12 12

Output
13



-----Note-----

In the first example, the score is maximized if the input sequence is split into two parts as (3, 4), (7, 2). It gives the total score of $(3 + 4 \operatorname{mod} 10) +(7 + 2 \operatorname{mod} 10) = 16$.

In the second example, the score is maximized if the first part consists of the first three elements, and the second part consists of the rest. Then, the score is $(16 + 3 + 24 \operatorname{mod} 12) +(13 + 9 + 8 + 7 + 5 + 12 + 12 \operatorname{mod} 12) = 7 + 6 = 13$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After a team finished their training session on Euro football championship, Valeric was commissioned to gather the balls and sort them into baskets. Overall the stadium has n balls and m baskets. The baskets are positioned in a row from left to right and they are numbered with numbers from 1 to m, correspondingly. The balls are numbered with numbers from 1 to n.

Valeric decided to sort the balls in the order of increasing of their numbers by the following scheme. He will put each new ball in the basket with the least number of balls. And if he's got several variants, he chooses the basket which stands closer to the middle. That means that he chooses the basket for which <image> is minimum, where i is the number of the basket. If in this case Valeric still has multiple variants, he chooses the basket with the minimum number.

For every ball print the number of the basket where it will go according to Valeric's scheme.

Note that the balls are sorted into baskets in the order of increasing numbers, that is, the first ball goes first, then goes the second ball and so on.

Input

The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 105) — the number of balls and baskets, correspondingly.

Output

Print n numbers, one per line. The i-th line must contain the number of the basket for the i-th ball.

Examples

Input

4 3


Output

2
1
3
2


Input

3 1


Output

1
1
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A sequence a=\{a_1,a_2,a_3,......\} is determined as follows:
 - The first term s is given as input.
 - Let f(n) be the following function: f(n) = n/2 if n is even, and f(n) = 3n+1 if n is odd.
 - a_i = s when i = 1, and a_i = f(a_{i-1}) when i > 1.
Find the minimum integer m that satisfies the following condition:
 - There exists an integer n such that a_m = a_n (m > n).

-----Constraints-----
 - 1 \leq s \leq 100
 - All values in input are integers.
 - It is guaranteed that all elements in a and the minimum m that satisfies the condition are at most 1000000.

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

-----Output-----
Print the minimum integer m that satisfies the condition.

-----Sample Input-----
8

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

a=\{8,4,2,1,4,2,1,4,2,1,......\}. As a_5=a_2, the answer is 5.

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