vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Big Number and Remainder

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Stepan has a very big positive integer.

Let's consider all cyclic shifts of Stepan's integer (if we look at his integer like at a string) which are also integers (i.e. they do not have leading zeros). Let's call such shifts as good shifts. For example, for the integer 10203 the good shifts are the integer itself 10203 and integers 20310 and 31020.

Stepan wants to know the minimum remainder of the division by the given number *m* among all good shifts. Your task is to determine the minimum remainder of the division by *m*.

Input Specification:
The first line contains the integer which Stepan has. The length of Stepan's integer is between 2 and 200<=000 digits, inclusive. It is guaranteed that Stepan's integer does not contain leading zeros.

The second line contains the integer *m* (2<=≤<=*m*<=≤<=108) — the number by which Stepan divides good shifts of his integer.

Output Specification:
Print the minimum remainder which Stepan can get if he divides all good shifts of his integer by the given number *m*.

Demo Input:
['521\n3\n', '1001\n5\n', '5678901234567890123456789\n10000\n']

Demo Output:
['2\n', '0\n', '123\n']

Note:
In the first example all good shifts of the integer 521 (good shifts are equal to 521, 215 and 152) has same remainder 2 when dividing by 3.

In the second example there are only two good shifts: the Stepan's integer itself and the shift by one position to the right. The integer itself is 1001 and the remainder after dividing it by 5 equals 1. The shift by one position to the right equals to 1100 and the remainder after dividing it by 5 equals 0, which is the minimum possible remainder.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Announcement
************Second Round will be ONLINE instead of ONSITE*************
Problem Statement

Dora bought n paint buckets (numbered as 0,1,2,...,n-1) of k distinct colors with Ci as the color of ith bucket. She arranges the buckets in a straight line according to their number in ascending order. She wants to mix all the paint buckets but in a very special way. ith paint bucket can be mixed only with either (i+1)th or (i-1)th bucket.

(a) If ith bucket is mixed with (i-1)th bucket the resulting number of the mixture will be i-1.The no on the buckets placed at (i+1)th,(i+2)th,...,(n-1)th will be decreased by 1. 

(b) If ith bucket is mixed with (i+1)th bucket the resulting number of the mixture will be i.The no of the buckets placed at (i+2)th,(i+3)th...,(n-1)th will be decreased by 1.  

She will continue mixing the paint until one bucket is left and no further mixing can be done.

Every such mixing requires some fixed no of seconds so that the paint get mixed thoroughly. T is a k x k matrix in which T(i,j) tells us how much seconds it take to mix the paint of colors i and j. 

If ith bucket with color Ci is mixed with jth bucket of Color Cj, the resultant color will be (Ci+Cj)mod(k) and time taken will be T(Ci,Cj).
See sample case for more explanation.

Dora wants to mix all the paint buckets in minimum possible time. Calculate the minimum possible time required for this task.

Input

First line contains t, no. of testcases.

First line of each test case contains two space separated integers n and k. Next line contains n space separated integers C0 C1 C2 ... Cn-1 , the color of the n paint buckets. 

Next k lines contains the rows for matrix T with each line containing k space separated integers. jth integer in the ith line is the time in seconds Dora takes to mix colours i and j.

Output

The minimum possible time(in seconds) she takes, to mix all the colors.

Constraints

1 ≤ t ≤ 10

1 ≤ n ≤ 100

1 ≤ k ≤ 100

0 ≤ Ci ≤ k-1

1 ≤ Tij ≤ 10000

Note: Mixing ith color with jth color is same as mixing jth color with ith color.

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

SAMPLE OUTPUT
3
2

Explanation

In the first case, she will mix bucket numbered 1 and 2 holding color 1 and 1 respectively. The resultant color is 2 ( (1+1)%3 ) and time taken for this process is 2 seconds. As 1st and 2nd bucket are mixed, the number of the mixture will be 1. 
Now 0th bucket and 1st bucket (newly obtained bucket) will be mixed giving a paint bucket of color 2 ( (0+2)%3 )and time taken for this process is 1 second.
Total time is 2+1=3 seconds.

Similarly for the second case.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today Oz is playing with colorful balls. He has A  red balls, B  blue balls, C  green balls and D yellow balls. Using the balls, he wants to make a colorful straight line such that no two balls of same type are adjacent to each other. He also knows that their are many ways to make colorful straight line keeping the condition so first he wants to know how many ways are their to make colorful straight line. Help Oz with the answer.

Note:
Each ball of a given type is identical to others of the same type, thus swapping the positions of two of the same type of balls does not make a new arrangement.

Input:
First and the only line of the input contains four single space separated integers i.e A, B, C  and D as described in the problem statement.

Output:
Output the number of ways to make a colorful straight line.

Constraints:
A , B, C and D ≤ 10

SAMPLE INPUT
2 2 0 0

SAMPLE OUTPUT
2

Explanation

There are two possible arrangements: RBRB or BRBR where 'B' indicates a blue ball and 'R' indicates a red ball.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Try guessing the statement from this picture:  $3$ 

You are given a non-negative integer $d$. You have to find two non-negative real numbers $a$ and $b$ such that $a + b = d$ and $a \cdot b = d$.


-----Input-----

The first line contains $t$ ($1 \le t \le 10^3$) — the number of test cases.

Each test case contains one integer $d$ $(0 \le d \le 10^3)$.


-----Output-----

For each test print one line.

If there is an answer for the $i$-th test, print "Y", and then the numbers $a$ and $b$.

If there is no answer for the $i$-th test, print "N".

Your answer will be considered correct if $|(a + b) - a \cdot b| \le 10^{-6}$ and $|(a + b) - d| \le 10^{-6}$.


-----Example-----
Input
7
69
0
1
4
5
999
1000

Output
Y 67.985071301 1.014928699
Y 0.000000000 0.000000000
N
Y 2.000000000 2.000000000
Y 3.618033989 1.381966011
Y 997.998996990 1.001003010
Y 998.998997995 1.001002005

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Recently Polycarpus has learned the "bitwise AND" operation (which is also called "AND") of non-negative integers. Now he wants to demonstrate the school IT teacher his superb manipulation with the learned operation.

For that Polycarpus came to school a little earlier and wrote on the board a sequence of non-negative integers *a*1,<=*a*2,<=...,<=*a**n*. He also wrote a square matrix *b* of size *n*<=×<=*n*. The element of matrix *b* that sits in the *i*-th row in the *j*-th column (we'll denote it as *b**ij*) equals:
 -  the "bitwise AND" of numbers *a**i* and *a**j* (that is, *b**ij*<==<=*a**i* &amp; *a**j*), if *i*<=≠<=*j*; -  -1, if *i*<==<=*j*. 
Having written out matrix *b*, Polycarpus got very happy and wiped *a* off the blackboard. But the thing is, the teacher will want this sequence to check whether Polycarpus' calculations were correct. Polycarus urgently needs to restore the removed sequence of integers, or else he won't prove that he can count correctly.

Help Polycarpus, given matrix *b*, restore the sequence of numbers *a*1,<=*a*2,<=...,<=*a**n*, that he has removed from the board. Polycarpus doesn't like large numbers, so any number in the restored sequence mustn't exceed 109.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=100) — the size of square matrix *b*. Next *n* lines contain matrix *b*. The *i*-th of these lines contains *n* space-separated integers: the *j*-th number represents the element of matrix *b**ij*. It is guaranteed, that for all *i* (1<=≤<=*i*<=≤<=*n*) the following condition fulfills: *b**ii* = -1. It is guaranteed that for all *i*,<=*j* (1<=≤<=*i*,<=*j*<=≤<=*n*; *i*<=≠<=*j*) the following condition fulfills: 0<=≤<=*b**ij*<=≤<=109, *b**ij*<==<=*b**ji*.

Output Specification:
Print *n* non-negative integers *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=≤<=109) — the sequence that Polycarpus wiped off the board. Separate the numbers by whitespaces. 

It is guaranteed that there is sequence *a* that satisfies the problem conditions. If there are multiple such sequences, you are allowed to print any of them.

Demo Input:
['1\n-1\n', '3\n-1 18 0\n18 -1 0\n0 0 -1\n', '4\n-1 128 128 128\n128 -1 148 160\n128 148 -1 128\n128 160 128 -1\n']

Demo Output:
['0 ', '18 18 0 ', '128 180 148 160 ']

Note:
If you do not know what is the "bitwise AND" operation please read: http://en.wikipedia.org/wiki/Bitwise_operation.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 The number is considered to be `unlucky` if it does not have digits `4` and `7` and is divisible by `13`. Please count all unlucky numbers not greater than `n`.

# Example

 For `n = 20`, the result should be `2` (numbers `0 and 13`).
 
 For `n = 100`, the result should be `7` (numbers `0, 13, 26, 39, 52, 65, and 91`)
 
# Input/Output


 - `[input]` integer `n`

 `1 ≤ n ≤ 10^8(10^6 in Python)`


 - `[output]` an integer

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko needs to choose four points in the plane so that they form a rectangle with sides parallel to the axes. He has already chosen three points and is confident that he hasn’t made a mistake, but is having trouble locating the last point. Help him.

-----Input-----
Each of the three points already chosen will be given on a separate line. All coordinates will be integers between $1$ and $1000$.

-----Output-----
Output the coordinates of the fourth vertex of the rectangle.

-----Examples-----
Sample Input:
5 5
5 7
7 5
Sample Output:
7 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You’re one of the king’s spies sent on a secret mission to retrieve an item of incredible value, an ancient scroll from the throne room. Legend has it, the scroll contains the answer to the $P$ versus $NP$ problem. When you finally reach the throne room, you realize there is a code the guards enter every day while observing them. As a spy, you’ve started to notice a few rules for each guard’s code:
 - each code is a matrix consisting of nonzero decimal digits (integers from $1$ to $9$) with $m$ rows and $n$ columns
 - no digit repeats within any row of the code
 - for each digit $l$ in the code, except for those in the topmost row and rightmost column, let $u$ be the digit above it and let $r$ be the digit to its right in the code matrix. Then one of the following must be true:
 - $u$ is the product of $l$ and $r$
 - $u$ is the sum of $l$ and $r$
 - $u$ is the difference of $l$ and $r$ or $r$ and $l$
 - $u$ is the quotient of $l$ and $r$ or $r$ and $l$

On day $999$, you’ve noticed a guard has seem to walked off while entering his code. Some digits have been omitted, but after careful consideration you think you can crack the code. Digits that have been omitted are represented with a $0$. How many complete codes are possible, given the guard’s partial code?

-----Input-----
A test case starts with a line containing two numbers $m$ ($3 \le m \le 6$) and $n$ ($3 \le n \le 6$), which is the number of rows and number of columns of the grid. The following $m$ lines contain $n$ integers from $0$ to $9$, separated by spaces. $0$ indicates an unknown value that you can supply, and there will be at most $\lfloor \frac{m*n}{2} \rfloor $ unknown values.

You can assume the guard has followed the rules with the partial code (i.e. no repeated digits appear in any row in the input, and any three pairs of non-zero digits that form an L have the property described above).

-----Output-----
For each test case, print the number of complete codes you can find.

-----Examples-----
Sample Input 1:
3 3
1 2 4
0 3 6
4 0 3
Sample Output 1:
2

Sample Input 2:
3 4
2 3 0 7
0 0 2 1
0 0 3 0
Sample Output 2:
37

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the hard version of the problem. The only difference is that in this version 1 ≤ q ≤ 10^5. You can make hacks only if both versions of the problem are solved.

There is a process that takes place on arrays a and b of length n and length n-1 respectively. 

The process is an infinite sequence of operations. Each operation is as follows: 

  * First, choose a random integer i (1 ≤ i ≤ n-1). 
  * Then, simultaneously set a_i = min\left(a_i, \frac{a_i+a_{i+1}-b_i}{2}\right) and a_{i+1} = max\left(a_{i+1}, \frac{a_i+a_{i+1}+b_i}{2}\right) without any rounding (so values may become non-integer). 

See notes for an example of an operation.

It can be proven that array a converges, i. e. for each i there exists a limit a_i converges to. Let function F(a, b) return the value a_1 converges to after a process on a and b.

You are given array b, but not array a. However, you are given a third array c. Array a is good if it contains only integers and satisfies 0 ≤ a_i ≤ c_i for 1 ≤ i ≤ n.

Your task is to count the number of good arrays a where F(a, b) ≥ x for q values of x. Since the number of arrays can be very large, print it modulo 10^9+7.

Input

The first line contains a single integer n (2 ≤ n ≤ 100).

The second line contains n integers c_1, c_2 …, c_n (0 ≤ c_i ≤ 100).

The third line contains n-1 integers b_1, b_2, …, b_{n-1} (0 ≤ b_i ≤ 100).

The fourth line contains a single integer q (1 ≤ q ≤ 10^5).

The fifth line contains q space separated integers x_1, x_2, …, x_q (-10^5 ≤ x_i ≤ 10^5).

Output

Output q integers, where the i-th integer is the answer to the i-th query, i. e. the number of good arrays a where F(a, b) ≥ x_i modulo 10^9+7.

Example

Input


3
2 3 4
2 1
5
-1 0 1 -100000 100000


Output


56
28
4
60
0

Note

The following explanation assumes b = [2, 1] and c=[2, 3, 4] (as in the sample).

Examples of arrays a that are not good: 

  * a = [3, 2, 3] is not good because a_1 > c_1; 
  * a = [0, -1, 3] is not good because a_2 < 0. 



One possible good array a is [0, 2, 4]. We can show that no operation has any effect on this array, so F(a, b) = a_1 = 0.

Another possible good array a is [0, 1, 4]. In a single operation with i = 1, we set a_1 = min((0+1-2)/(2), 0) and a_2 = max((0+1+2)/(2), 1). So, after a single operation with i = 1, a becomes equal to [-1/2, 3/2, 4]. We can show that no operation has any effect on this array, so F(a, b) = -1/2.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Max wants to buy a new skateboard. He has calculated the amount of money that is needed to buy a new skateboard. He left a calculator on the floor and went to ask some money from his parents. Meanwhile his little brother Yusuf came and started to press the keys randomly. Unfortunately Max has forgotten the number which he had calculated. The only thing he knows is that the number is divisible by 4.

You are given a string *s* consisting of digits (the number on the display of the calculator after Yusuf randomly pressed the keys). Your task is to find the number of substrings which are divisible by 4. A substring can start with a zero.

A substring of a string is a nonempty sequence of consecutive characters.

For example if string *s* is 124 then we have four substrings that are divisible by 4: 12, 4, 24 and 124. For the string 04 the answer is three: 0, 4, 04.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use gets/scanf/printf instead of getline/cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input Specification:
The only line contains string *s* (1<=≤<=|*s*|<=≤<=3·105). The string *s* contains only digits from 0 to 9.

Output Specification:
Print integer *a* — the number of substrings of the string *s* that are divisible by 4.

Note that the answer can be huge, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.

Demo Input:
['124\n', '04\n', '5810438174\n']

Demo Output:
['4\n', '3\n', '9\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nobody knows, but $N$ frogs live in Chef's garden.
Now they are siting on the X-axis and want to speak to each other. One frog can send a message to another one if the distance between them is less or equal to $K$.
Chef knows all $P$ pairs of frogs, which want to send messages. Help him to define can they or not!
Note : More than $1$ frog can be on the same point on the X-axis.

-----Input-----
- The first line contains three integers $N$, $K$ and $P$.
- The second line contains $N$ space-separated integers $A_1$, $A_2$, …, $A_N$ denoting the x-coordinates of frogs".
- Each of the next $P$ lines contains two integers $A$ and $B$ denoting the numbers of frogs according to the input.

-----Output-----
For each pair print "Yes" without a brackets if frogs can speak and "No" if they cannot.

-----Constraints-----
- $1 \le N, P \le 10^5$
- $0 \le A_i, K \le 10^9$
- $1 \le A, B \le N$

-----Example-----

-----Sample Input:-----
5 3 3
0 3 8 5 12
1 2
1 3
2 5

-----Sample Output:-----
Yes
Yes
No

-----Explanation-----
- 
For pair $(1, 2)$ frog $1$ can directly speak to the frog $2$ as the distance between them is $3 - 0 = 3 \le K$ . 
- 
For pair $(1, 3)$ frog $1$ can send a message to frog $2$, frog $2$ can send it to frog $4$ and it can send it to frog $3$.
- 
For pair $(2, 5)$ frogs can't send a message under current constraints.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day while playing with parentheses '{' and '}' , Panda came across an interesting question , given a string A consisting of parentheses we've to perform the following operation: Given two integers L and R,find the length of correct parentheses subsequence.

Note: All the indices (L and R) for above operation are according to 1 indexed.  

INPUT: 
First line of input contains a string comprising of parentheses '{'and '}'.
Second line contains T the number of queries. 
Next T lines contains two space separated integers L and R.

OUTPUT:
For each query print length of correct parentheses subsequence in new line. 

Constraints
1 ≤ |Length of the string| ≤ 10^5
1 ≤ T ≤ 10^5  
1 ≤ L ≤ R ≤ 10^5    

SAMPLE INPUT
{{}}{
5
1 2
1 4
2 3
1 5
2 4

SAMPLE OUTPUT
0
4
2
4
2

Explanation

For Query 1: correct Bracket subseqence length is 0 {{.  
For Query 5: correct Bracket subseqence length is 2 {}}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Back in 2015, Usain Bolt announced that he'll be retiring after the 2017 World Championship. Though his final season did not end gloriously, we all know that he is a true legend and we witnessed his peak during 2008 - 2013. 
Post retirement, Usain Bolt is still leading an adventurous life. He's exploring the unexplored parts of the globe. But sometimes he gets bored, and reads questions asked about him on Quora. One such question he read was, "Who would win a race between Usain Bolt and a tiger if the race is on a straight line track and the tiger is $distancetoBolt$ meters behind Bolt? The finishing point is $finish$ meters away from Bolt's starting position. The tiger starts with an initial speed of $0$ $meter/second$, and will accelerate itself with $tigerAccelaration$ $m/s^2$. Bolt can run with a constant speed of $boltSpeed$ $m/s$ from start to finish. Given these values, find out who will win the race - Bolt or the tiger? "
Note that Bolt will win the race if and only if he touches the finishing line before the tiger touches it. If both of them finish together, the tiger is announced as the winner since Bolt was given an initial advantage. See the figure below for more clarity.

Since Bolt was busy practicing in the tracks during his Physics school classes, he is asking for your help to solve the question. Can you please help him?
He just remembers two formulae from the class, and thinks that they will be useful to you:
$Displacement (S) $ = $ut$ +$ (1/2)at^2$ where $u$ is the initial velocity , #$ $is the acceleration and $t$ is the time taken.
$Velocity$ = $Displacement /Time$

-----Input:-----
- The first line will contain $T$, the number of testcases. Then the description of each test case follow. 
- Each test case contains 4 integers $finish, distancetoBolt, tigerAccelaration, boltSpeed$. 

-----Output:-----
For each testcase, output in a single line, the word "Bolt" or "Tiger" without quotes, depending on whether Bolt wins or the tiger wins.

-----Constraints-----
- $1 \leq T \leq 100000$
- $1 \leq finish\leq 10^5$
- $1 \leq distancetoBolt\leq 10^5$
- $1 \leq tigerAccelaration\leq 10^5$
- $1 \leq boltSpeed\leq 10^5$

-----Sample Input:-----
2
10 100 10 10
100 10 5 10

-----Sample Output:-----
Bolt
Tiger

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Barry and Bruce are twin brothers. Bruce likes keeping his parenthetical sequences balanced. Barry would like to mess with Bruce by performing some operations on the sequence. Each operation is one of the following:
 - Change a single ‘(’ to a ‘)’ in the sequence.
 - Change a single ‘)’ to a ‘(’ in the sequence.

Bruce will attempt to rebalance the parenthetical sequence by performing the same operations. Bruce does not like tedium and will perform no more than $k$ operations to balance the sequence.

A balanced parenthetical sequence is defined as:
 - The empty string
 - $AB$ where $A$ and $B$ are both balanced parenthetical sequences
 - ($A$) where $A$ is a balanced parenthetical sequence

Barry would like to disrupt the sequence to the point where it is impossible for Bruce to rebalance the sequence in $k$ moves. Changing some position in the sequence requires effort and the amount of effort varies by position. Some positions are even delightful to switch and require negative effort. Each position can be changed at most once.

Barry hates effort and would like to compute the minimum sum of effort to ensure that Bruce cannot balance the sequence.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will contain two integers $n$ and $k$, where $n$ ($1 \le n \le 10^5$) is the length of the sequence, and $k$ ($0 \le k \le n$) is the maximum number of moves for Bruce.

The next line contains a single string of length $n$ consisting of only the characters ‘(’ and ‘)’. This string is NOT required to be balanced.

The next $n$ lines will each contain a single integer $c$ ($-1000 \le c \le 1000$), which is the cost of changing each parenthesis in order.

-----Output-----
Output a single integer, which is the minimum sum of effort of moves required to make the string impossible to be balanced by Bruce. If Bruce can always rebalance the string regardless of Barry’s actions, print a single question mark (‘?’).

-----Examples-----
Sample Input:
4 1
((()
480
617
-570
928
Sample Output:
480

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