vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Polycarp's workday lasts exactly $n$ minutes. He loves chocolate bars and can eat one bar in one minute. Today Polycarp has $k$ bars at the beginning of the workday.

In some minutes of the workday Polycarp has important things to do and in such minutes he is not able to eat a chocolate bar. In other minutes he can either eat or not eat one chocolate bar. It is guaranteed, that in the first and in the last minutes of the workday Polycarp has no important things to do and he will always eat bars in this minutes to gladden himself at the begining and at the end of the workday. Also it is guaranteed, that $k$ is strictly greater than $1$.

Your task is to determine such an order of eating chocolate bars that the maximum break time between eating bars is as minimum as possible.

Consider that Polycarp eats a bar in the minute $x$ and the next bar in the minute $y$ ($x < y$). Then the break time is equal to $y - x - 1$ minutes. It is not necessary for Polycarp to eat all bars he has.


-----Input-----

The first line contains two integers $n$ and $k$ ($2 \le n \le 200\,000$, $2 \le k \le n$) — the length of the workday in minutes and the number of chocolate bars, which Polycarp has in the beginning of the workday.

The second line contains the string with length $n$ consisting of zeros and ones. If the $i$-th symbol in the string equals to zero, Polycarp has no important things to do in the minute $i$ and he can eat a chocolate bar. In the other case, Polycarp is busy in the minute $i$ and can not eat a chocolate bar. It is guaranteed, that the first and the last characters of the string are equal to zero, and Polycarp always eats chocolate bars in these minutes.


-----Output-----

Print the minimum possible break in minutes between eating chocolate bars.


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

Output
1

Input
8 3
01010110

Output
3



-----Note-----

In the first example Polycarp can not eat the chocolate bar in the second minute, so the time of the break equals to one minute.

In the second example Polycarp will eat bars in the minutes $1$ and $8$ anyway, also he needs to eat the chocolate bar in the minute $5$, so that the time of the maximum break will be equal to $3$ minutes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko got his driver’s license! To celebrate that joyous occasion, his parents bought him his first car: a monster truck! Mirko found out that even though having a car that can squash all other cars is nice in traffic jams, parking a car that is the size of $4$ normal cars can be a bit tricky.

His friend, Slavko, works part time in the city parking company. He periodically sends Mirko a map of the city with occupied parking spaces marked. The map can be represented as a table with $R$ rows, $C$ columns each. Each cell can contain a building (symbol ‘#’), a parked car (symbol ‘X’) or a free parking space (symbol ‘.’). A monster truck is quite huge, $2$ by $2$ cells to be exact.

Help Mirko calculate the number of possible parking spaces grouped by the number of cars he needs to squash to park in them. We are only interested in the number of cars Mirko will squash on the parking space, not the number of cars he will squash on the way over. However, Mirko can’t park on a building. Not even a monster truck is large enough to squash buildings!

-----Input-----
The first line of input contains two integers, $R$ and $C$ ($2 \leq R, C \leq 50$), the number of rows and columns of the map. The next $R$ lines contain $C$ characters each. Only characters ‘#’, ‘X’ and ‘.’ appear in the input. Note that ‘X’ will always be capital.

-----Output-----
The output consists of five lines, the total number of parking spaces Mirko can park on if he squashes $0$ cars (first line), $1$ car (second line), $2$ cars (third line), $3$ cars (fourth line), $4$ cars (fifth line).

-----Examples-----
Sample Input 1:
4 4
#..#
..X.
..X.
#XX#
Sample Output 1:
1
1
2
1
0

Sample Input 2:
4 4
....
....
....
....
Sample Output 2:
9
0
0
0
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya likes horse racing very much. Horses numbered from l to r take part in the races. Petya wants to evaluate the probability of victory; for some reason, to do that he needs to know the amount of nearly lucky horses' numbers. A nearly lucky number is an integer number that has at least two lucky digits the distance between which does not exceed k. Petya learned from some of his mates from Lviv that lucky digits are digits 4 and 7. The distance between the digits is the absolute difference between their positions in the number of a horse. For example, if k = 2, then numbers 412395497, 404, 4070400000070004007 are nearly lucky and numbers 4, 4123954997, 4007000040070004007 are not.

Petya prepared t intervals [li, ri] and invented number k, common for all of them. Your task is to find how many nearly happy numbers there are in each of these segments. Since the answers can be quite large, output them modulo 1000000007 (109 + 7).

Input

The first line contains two integers t and k (1 ≤ t, k ≤ 1000) — the number of segments and the distance between the numbers correspondingly. Next t lines contain pairs of integers li and ri (1 ≤ l ≤ r ≤ 101000). All numbers are given without the leading zeroes. Numbers in each line are separated by exactly one space character.

Output

Output t lines. In each line print one integer — the answer for the corresponding segment modulo 1000000007 (109 + 7).

Examples

Input

1 2
1 100


Output

4


Input

1 2
70 77


Output

2


Input

2 1
1 20
80 100


Output

0
0

Note

In the first sample, the four nearly lucky numbers are 44, 47, 74, 77.

In the second sample, only 74 and 77 are in the given segment.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Maxim always goes to the supermarket on Sundays. Today the supermarket has a special offer of discount systems.

There are m types of discounts. We assume that the discounts are indexed from 1 to m. To use the discount number i, the customer takes a special basket, where he puts exactly q_{i} items he buys. Under the terms of the discount system, in addition to the items in the cart the customer can receive at most two items from the supermarket for free. The number of the "free items" (0, 1 or 2) to give is selected by the customer. The only condition imposed on the selected "free items" is as follows: each of them mustn't be more expensive than the cheapest item out of the q_{i} items in the cart.

Maxim now needs to buy n items in the shop. Count the minimum sum of money that Maxim needs to buy them, if he use the discount system optimally well.

Please assume that the supermarket has enough carts for any actions. Maxim can use the same discount multiple times. Of course, Maxim can buy items without any discounts.


-----Input-----

The first line contains integer m (1 ≤ m ≤ 10^5) — the number of discount types. The second line contains m integers: q_1, q_2, ..., q_{m} (1 ≤ q_{i} ≤ 10^5). 

The third line contains integer n (1 ≤ n ≤ 10^5) — the number of items Maxim needs. The fourth line contains n integers: a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^4) — the items' prices.

The numbers in the lines are separated by single spaces.


-----Output-----

In a single line print a single integer — the answer to the problem.


-----Examples-----
Input
1
2
4
50 50 100 100

Output
200

Input
2
2 3
5
50 50 50 50 50

Output
150

Input
1
1
7
1 1 1 1 1 1 1

Output
3



-----Note-----

In the first sample Maxim needs to buy two items that cost 100 and get a discount for two free items that cost 50. In that case, Maxim is going to pay 200.

In the second sample the best strategy for Maxim is to buy 3 items and get 2 items for free using the discount. In that case, Maxim is going to pay 150.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a circle of length C, and you are placing N arcs on it. Arc i has length L_i.

Every arc i is placed on the circle uniformly at random: a random real point on the circle is chosen, then an arc of length L_i centered at this point appears.

Note that the arcs are placed independently. For example, they may intersect or contain each other.

What is the probability that every real point of the circle will be covered by at least one arc? Assume that an arc covers its ends.

Constraints

* 2 \leq N \leq 6
* 2 \leq C \leq 50
* 1 \leq L_i < C
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N C
L_1 L_2 ... L_N


Output

Print the probability that every real point of the circle will be covered by at least one arc. Your answer will be considered correct if its absolute error doesn't exceed 10^{-11}.

Examples

Input

2 3
2 2


Output

0.3333333333333333


Input

4 10
1 2 3 4


Output

0.0000000000000000


Input

4 2
1 1 1 1


Output

0.5000000000000000


Input

3 5
2 2 4


Output

0.4000000000000000


Input

4 6
4 1 3 2


Output

0.3148148148148148


Input

6 49
22 13 27 8 2 19


Output

0.2832340720702695

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
It is known that there are *k* fish species in the polar ocean, numbered from 1 to *k*. They are sorted by non-decreasing order of their weight, which is a positive number. Let the weight of the *i*-th type of fish be *w**i*, then 0<=&lt;<=*w*1<=≤<=*w*2<=≤<=...<=≤<=*w**k* holds.

Polar bears Alice and Bob each have caught some fish, and they are guessing who has the larger sum of weight of the fish he/she's caught. Given the type of the fish they've caught, determine whether it is possible that the fish caught by Alice has a strictly larger total weight than Bob's. In other words, does there exist a sequence of weights *w**i* (not necessary integers), such that the fish caught by Alice has a strictly larger total weight?

Input Specification:
The first line contains three integers *n*,<=*m*,<=*k* (1<=≤<=*n*,<=*m*<=≤<=105,<=1<=≤<=*k*<=≤<=109) — the number of fish caught by Alice and Bob respectively, and the number of fish species.

The second line contains *n* integers each from 1 to *k*, the list of fish type caught by Alice. The third line contains *m* integers each from 1 to *k*, the list of fish type caught by Bob.

Note that one may have caught more than one fish for a same species.

Output Specification:
Output "YES" (without quotes) if it is possible, and "NO" (without quotes) otherwise.

Demo Input:
['3 3 3\n2 2 2\n1 1 3\n', '4 7 9\n5 2 7 3\n3 5 2 7 3 8 7\n']

Demo Output:
['YES\n', 'NO\n']

Note:
In the first sample, if *w*<sub class="lower-index">1</sub> = 1, *w*<sub class="lower-index">2</sub> = 2, *w*<sub class="lower-index">3</sub> = 2.5,  then Alice has a total of 2 + 2 + 2 = 6 weight units, while Bob only has 1 + 1 + 2.5 = 4.5.

In the second sample, the fish that Alice caught is a subset of Bob's. Therefore, the total weight of Bob’s fish is always not less than the total weight of Alice’s fish.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
The provided code stub reads two integers, a and b, from STDIN.
Add logic to print two lines. The first line should contain the result of integer division,
a // b. The second line should contain the result of float division, a / b.
No rounding or formatting is necessary.

=====Example=====
a = 3
b = 5
The result of the integer division 3//5 = 0.
The result of the float division is 3/5 = 0.6. 

Print:
0
0.6

=====Input Format=====
The first line contains the first integer, a.
The second line contains the second integer, b.

=====Output Format=====
Print the two lines as described above.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an unusual problem in an unusual contest, here is the announcement: [http://codeforces.com/blog/entry/73543](//codeforces.com/blog/entry/73543)

You are given an array A of length n, initially filled with zeros. You need to process q queries to the array, each of one of the following types: 

  1. 1 x y: you need to assign A_x=y; 
  2. 2 l r: you need to print ∑_{i=l}^r A_i. 

Furthermore, there are T independent tests you need to process.

Input

The first line contains an integer T (1 ≤ T ≤ 10^5) — the number of test cases.

Each test case description starts with two integers n, q (1 ≤ n, q ≤ 10^5) — the length of the array and the number of queries. The following q lines contain the description of queries: 1~x~y (1 ≤ x ≤ n, 0 ≤ y ≤ 10^9) for queries of the first type and 2~l~r (1 ≤ l ≤ r ≤ n) for queries of the second type. 

It is guaranteed that the sum of n as well as the sum of q does not exceed 10^6.

Output

For each query of the second type print its result on a separate line.

Example

Input


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


Output


0
2
5
11

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vus the Cossack holds a programming competition, in which $n$ people participate. He decided to award them all with pens and notebooks. It is known that Vus has exactly $m$ pens and $k$ notebooks.

Determine whether the Cossack can reward all participants, giving each of them at least one pen and at least one notebook.


-----Input-----

The first line contains three integers $n$, $m$, and $k$ ($1 \leq n, m, k \leq 100$) — the number of participants, the number of pens, and the number of notebooks respectively.


-----Output-----

Print "Yes" if it possible to reward all the participants. Otherwise, print "No".

You can print each letter in any case (upper or lower).


-----Examples-----
Input
5 8 6

Output
Yes

Input
3 9 3

Output
Yes

Input
8 5 20

Output
No



-----Note-----

In the first example, there are $5$ participants. The Cossack has $8$ pens and $6$ notebooks. Therefore, he has enough pens and notebooks.

In the second example, there are $3$ participants. The Cossack has $9$ pens and $3$ notebooks. He has more than enough pens but only the minimum needed number of notebooks.

In the third example, there are $8$ participants but only $5$ pens. Since the Cossack does not have enough pens, the answer is "No".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a given list of strings where each string contains only lowercase letters from $a-j$, inclusive. The set of strings is said to be a GOOD SET if no string is a prefix of another string.  In this case, print GOOD SET.  Otherwise, print BAD SET on the first line followed by the string being checked. 

Note If two strings are identical, they are prefixes of each other.

Example 

$words=[\text{'abcd'},\text{'bcd'},\text{'abcd'},\text{'bcde'}]$     

Here 'abcd' is a prefix of 'abcde' and 'bcd' is a prefix of 'bcde'.  Since 'abcde' is tested first, print 

BAD SET  
abcde

$words=[\text{'ab'},\text{'bc'},\text{'cd'}]$.   

No string is a prefix of another so print 

GOOD SET 

Function Description 

Complete the noPrefix function in the editor below.  

noPrefix has the following parameter(s): 

- string words[n]: an array of strings  

Prints 

-   string(s): either GOOD SET or BAD SET on one line followed by the word on the next line.  No return value is expected.  

Input Format 

First line contains $n$, the size of $words[]$. 

Then next $n$ lines each contain a string, $words[i]$.   

Constraints 

$1\leq n\leq10^5$ 

$1\leq$ the length of words[i] $\leq60$ 

All letters in $words[i]$ are in the range 'a' through 'j', inclusive.    

Sample Input00  

STDIN       Function
-----       --------
7            words[] size n = 7
aab          words = ['aab', 'defgab', 'abcde', 'aabcde', 'bbbbbbbbbb', 'jabjjjad']
defgab  
abcde
aabcde
cedaaa
bbbbbbbbbb
jabjjjad

Sample Output00  

BAD SET
aabcde

Explanation 

'aab' is prefix of 'aabcde' so it is a BAD SET and fails at string 'aabcde'.  

Sample Input01

4
aab
aac
aacghgh
aabghgh

Sample Output01  

BAD SET
aacghgh

Explanation 

'aab' is a prefix of 'aabghgh', and aac' is prefix of 'aacghgh'. The set is a BAD SET.   'aacghgh' is tested before 'aabghgh', so and it fails at 'aacghgh'.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation P of length N (1-based) is called good if it satisfies the following these conditions:
For each 1 ≤ i ≤ N, P_{i} \neq i
|P_{1} - 1| \oplus |P_{2} - 2| \oplus \ldots \oplus |P_{N} - N| = 0

Here, \oplus denotes the [bitwise XOR operation] and |X| denotes the absolute value of X.

Find any good permutation P of length N or print -1 if no such permutation exists.

Note: A permutation of length N is an array which contains every integer from 1 to N (inclusive) exactly once.

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

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first and only line of each test case contains an integer N - the length of the permutation P.

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

For each test case, print -1 if no such permutation exists. Otherwise, in a single line, output N space-separated integers - the required good permutation. If more than one solution exists, you may print any of them.

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

$1 ≤ T ≤ 10^{6}$
$1 ≤ N ≤ 10^{6}$
- Sum of $N$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
3
1
2
8
----- Sample Output 1 ------ 
-1
2 1
7 1 5 6 3 4 8 2
----- explanation 1 ------ 
Test case 1: There is only one permutation $P = [1]$ of length $1$. Since $P_{1} = 1$ the answer does not exist.

Test case 2: Consider the permutation $P = [2, 1]$. Both conditions are satisfied.
* $P_{1} \neq 1$ and $P_{2} \neq 2$
* $|P_{1} - 1| \oplus |P_{2} - 2| = |2 - 1| \oplus |1 - 2| = 1 \oplus 1 = 0$

Test case 3: Both conditions are satisfied for $P = [7, 1, 5, 6, 3, 4, 8, 2]$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Allen is playing Number Clicker on his phone.

He starts with an integer $u$ on the screen. Every second, he can press one of 3 buttons.
 1.  Turn $u \to u+1 \pmod{p}$. 1.  Turn $u \to u+p-1 \pmod{p}$. 1.  Turn $u \to u^{p-2} \pmod{p}$. 
Allen wants to press at most 200 buttons and end up with $v$ on the screen. Help him!

Input Specification:
The first line of the input contains 3 positive integers: $u, v, p$ ($0 \le u, v \le p-1$, $3 \le p \le 10^9 + 9$). $p$ is guaranteed to be prime.

Output Specification:
On the first line, print a single integer $\ell$, the number of button presses. On the second line, print integers $c_1, \dots, c_\ell$, the button presses. For $1 \le i \le \ell$, $1 \le c_i \le 3$.

We can show that the answer always exists.

Demo Input:
['1 3 5\n', '3 2 5\n']

Demo Output:
['2\n1 1\n', '1\n3\n']

Note:
In the first example the integer on the screen changes as $1 \to 2 \to 3$.

In the second example the integer on the screen changes as $3 \to 2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivar the Boneless is a great leader. He is trying to capture Kattegat from Lagertha. The war has begun and wave after wave Ivar's warriors are falling in battle.

Ivar has $n$ warriors, he places them on a straight line in front of the main gate, in a way that the $i$-th warrior stands right after $(i-1)$-th warrior. The first warrior leads the attack.

Each attacker can take up to $a_i$ arrows before he falls to the ground, where $a_i$ is the $i$-th warrior's strength.

Lagertha orders her warriors to shoot $k_i$ arrows during the $i$-th minute, the arrows one by one hit the first still standing warrior. After all Ivar's warriors fall and all the currently flying arrows fly by, Thor smashes his hammer and all Ivar's warriors get their previous strengths back and stand up to fight again. In other words, if all warriors die in minute $t$, they will all be standing to fight at the end of minute $t$.

The battle will last for $q$ minutes, after each minute you should tell Ivar what is the number of his standing warriors.


-----Input-----

The first line contains two integers $n$ and $q$ ($1 \le n, q \leq 200\,000$) — the number of warriors and the number of minutes in the battle.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) that represent the warriors' strengths.

The third line contains $q$ integers $k_1, k_2, \ldots, k_q$ ($1 \leq k_i \leq 10^{14}$), the $i$-th of them represents Lagertha's order at the $i$-th minute: $k_i$ arrows will attack the warriors.


-----Output-----

Output $q$ lines, the $i$-th of them is the number of standing warriors after the $i$-th minute.


-----Examples-----
Input
5 5
1 2 1 2 1
3 10 1 1 1

Output
3
5
4
4
3

Input
4 4
1 2 3 4
9 1 10 6

Output
1
4
4
1



-----Note-----

In the first example:   after the 1-st minute, the 1-st and 2-nd warriors die.  after the 2-nd minute all warriors die (and all arrows left over are wasted), then they will be revived thus answer is 5 — all warriors are alive.  after the 3-rd minute, the 1-st warrior dies.  after the 4-th minute, the 2-nd warrior takes a hit and his strength decreases by 1.  after the 5-th minute, the 2-nd warrior dies.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let's introduce a number system which is based on a roman digits. There are digits I, V, X, L which correspond to the numbers $1$, $5$, $10$ and $50$ respectively. The use of other roman digits is not allowed.

Numbers in this system are written as a sequence of one or more digits. We define the value of the sequence simply as the sum of digits in it.

For example, the number XXXV evaluates to $35$ and the number IXI — to $12$.

Pay attention to the difference to the traditional roman system — in our system any sequence of digits is valid, moreover the order of digits doesn't matter, for example IX means $11$, not $9$.

One can notice that this system is ambiguous, and some numbers can be written in many different ways. Your goal is to determine how many distinct integers can be represented by exactly $n$ roman digits I, V, X, L.

Input Specification:
The only line of the input file contains a single integer $n$ ($1 \le n \le 10^9$) — the number of roman digits to use.

Output Specification:
Output a single integer — the number of distinct integers which can be represented using $n$ roman digits exactly.

Demo Input:
['1\n', '2\n', '10\n']

Demo Output:
['4\n', '10\n', '244\n']

Note:
In the first sample there are exactly $4$ integers which can be represented — I, V, X and L.

In the second sample it is possible to represent integers $2$ (II), $6$ (VI), $10$ (VV), $11$ (XI), $15$ (XV), $20$ (XX), $51$ (IL), $55$ (VL), $60$ (XL) and $100$ (LL).

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