vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A robot on an infinite grid starts at point (0, 0) and faces north.  The robot can receive one of three possible types of commands:

-2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units

Some of the grid squares are obstacles. 
The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])
If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)
Return the square of the maximum Euclidean distance that the robot will be from the origin.
 
Example 1:
Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)


Example 2:
Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)


 
Note:

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
The answer is guaranteed to be less than 2 ^ 31.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the fraction, $a/b$, where $a$ and $b$ are positive integers. If $a < b$ and $GCD(a,b) = 1$, it is called a reduced proper fraction.
If we list the set of a reduced proper fraction for $d \leq 8$, (where $d$ is the denominator) in ascending order of size, we get:
$1/8$, $1/7$, $1/6$, $1/5$, $1/4$, $2/7$, $1/3$, $3/8$, $2/5$ , $3/7$, $1/2$, $4/7$, $3/5$, $5/8$, $2/3$, $5/7$, $3/4$, $4/5$,  $5/6$, $6/7$, $7/8$
It can be seen that $2/5$ is the fraction immediately to the left of $3/7$.
By listing the set of reduced proper fractions for $d \leq N$ in ascending order of value, find the numerator and denominator of the fraction immediately to the left of $a/b$ when $a$ and $b$ are given.

-----Input:-----
- First line of input contains an integer $T$, number of test cases
- Next $T$ lines contain $a$ $b$ $N$ separated by space

-----Output:-----
Print the numerator and denominator separated by a space corresponding to each test case on a new line

-----Constraints-----
- $1 \leq T \leq 50$
- $1 \leq a < b \leq 10^9$
- $GCD(a,b) = 1$
- $b < N \leq 10^{15}$

-----Subtasks-----
- 10 points: $1 \leq N \leq 100$
- 30 points : $1 \leq N \leq 10^6$
- 60 points : $1 \leq N \leq 10^{15}$

-----Sample Input:-----
5
3 7 8
3 5 8
4 5 8
6 7 8
1 5 8

-----Sample Output:-----
2 5
4 7
3 4
5 6
1 6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sagheer is playing a game with his best friend Soliman. He brought a tree with n nodes numbered from 1 to n and rooted at node 1. The i-th node has a_{i} apples. This tree has a special property: the lengths of all paths from the root to any leaf have the same parity (i.e. all paths have even length or all paths have odd length).

Sagheer and Soliman will take turns to play. Soliman will make the first move. The player who can't make a move loses.

In each move, the current player will pick a single node, take a non-empty subset of apples from it and do one of the following two things:  eat the apples, if the node is a leaf.  move the apples to one of the children, if the node is non-leaf. 

Before Soliman comes to start playing, Sagheer will make exactly one change to the tree. He will pick two different nodes u and v and swap the apples of u with the apples of v.

Can you help Sagheer count the number of ways to make the swap (i.e. to choose u and v) after which he will win the game if both players play optimally? (u, v) and (v, u) are considered to be the same pair.


-----Input-----

The first line will contain one integer n (2 ≤ n ≤ 10^5) — the number of nodes in the apple tree.

The second line will contain n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^7) — the number of apples on each node of the tree.

The third line will contain n - 1 integers p_2, p_3, ..., p_{n} (1 ≤ p_{i} ≤ n) — the parent of each node of the tree. Node i has parent p_{i} (for 2 ≤ i ≤ n). Node 1 is the root of the tree.

It is guaranteed that the input describes a valid tree, and the lengths of all paths from the root to any leaf will have the same parity.


-----Output-----

On a single line, print the number of different pairs of nodes (u, v), u ≠ v such that if they start playing after swapping the apples of both nodes, Sagheer will win the game. (u, v) and (v, u) are considered to be the same pair.


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

Output
1

Input
3
1 2 3
1 1

Output
0

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

Output
4



-----Note-----

In the first sample, Sagheer can only win if he swapped node 1 with node 3. In this case, both leaves will have 2 apples. If Soliman makes a move in a leaf node, Sagheer can make the same move in the other leaf. If Soliman moved some apples from a root to a leaf, Sagheer will eat those moved apples. Eventually, Soliman will not find a move.

In the second sample, There is no swap that will make Sagheer win the game.

Note that Sagheer must make the swap even if he can win with the initial tree.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is playing an easier variation of the board game ‘Risk’ with his friend Mike. There is an $N * M$ grid, depicting the world map. Each cell of the grid is either $1$ or $0$ where $1$ denotes that there is land on this cell, while $0$ denotes water. 

In a turn, a player can capture an uncaptured cell that has land, and keep capturing neighbouring cells that share a side with it if they are on land. A cell once captured by a player can't be captured again by another player. The game continues till no uncaptured cell has land. Each player wants to be in control of as many cells of land as possible in total when the game finishes. Find the maximum number of cells of land that Chef can capture if he plays second, and both players play optimally. 

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow.
Each testcase contains $N + 1$ lines of input.
First line will contain $2$ space separated integers $N$ and $M$ denoting the size of the grid. 
Each of the next $N$ lines contains a binary string of length $M$ depicting the map. 

------ Output: ------
For each testcase, output in a single line answer to the problem.

------ Constraints  ------
$1 ≤ N, M ≤ 10^{5}$
Each character in the grid is either $0$ or $1$
There's atleast $1$ land on the grid
Sum of $N * M$ over all testcases is almost $10^{6}$.

----- Sample Input 1 ------ 
3

4 4

1001

0110

0110

1001

2 2

11

11

3 3

100

010

001
----- Sample Output 1 ------ 
2

0

1
----- explanation 1 ------ 
In test case 1, if both players play optimally, it takes $5$ steps to finish the game:

Step 1: First Mike chooses the cells $\{(2, 2), (2, 3), (3, 2), (3, 3)\}$ adding $4$ to his score.

Step 2: Second Chef chooses the cell $\{(1, 1)\}$ adding $1$ to his score.

Step 3: Next Mike chooses the cell $\{(1, 4)\}$ adding $1$ to his score.

Step 4: Next Chef chooses the cell $\{(4, 1)\}$ adding $1$ to his score.

Step 5: Finally, Mike chooses the cell $\{(4, 4)\}$ adding $1$ to his score.

Hence total score of Chef is $1 + 1 = 2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
AtCoder Inc. holds a contest every Saturday.
There are two types of contests called ABC and ARC, and just one of them is held at a time.
The company holds these two types of contests alternately: an ARC follows an ABC and vice versa.
Given a string S representing the type of the contest held last week, print the string representing the type of the contest held this week.

-----Constraints-----
 - S is ABC or ARC.

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

-----Output-----
Print the string representing the type of the contest held this week.

-----Sample Input-----
ABC

-----Sample Output-----
ARC

They held an ABC last week, so they will hold an ARC this week.

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

In China，there is an ancient mathematical book, called "The Mathematical Classic of Sun Zi"(《孙子算经》). In the book, there is a classic math problem: “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？” 

Ahh, Sorry. I forgot that you don't know Chinese. Let's translate it to English:

There is a unkown positive integer `n`. We know: 

`n % 3 = 2`, and `n % 5 = 3`, and `n % 7 = 2`. 

What's the minimum possible positive integer `n`?

The correct answer is `23`.

# Task

You are given three non-negative integers `x,y,z`. They represent the remainders of the unknown positive integer `n` divided by 3,5,7.

That is: `n % 3 = x, n % 5 = y, n % 7 = z`

Your task is to find the minimum possible positive integer `n` and return it.

# Example

For `x = 2, y = 3, z = 2`, the output should be `23`

`23 % 3 = 2, 23 % 5 = 3, 23 % 7 = 2`

For `x = 1, y = 2, z = 3`, the output should be `52`

`52 % 3 = 1, 52 % 5 = 2, 52 % 7 = 3`

For `x = 1, y = 3, z = 5`, the output should be `103`

`103 % 3 = 1, 103 % 5 = 3, 103 % 7 = 5`

For `x = 0, y = 0, z = 0`, the output should be `105`

For `x = 1, y = 1, z = 1`, the output should be `1`

# Note

- `0 <= x < 3, 0 <= y < 5, 0 <= z < 7`

- Happy Coding `^_^`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Per is obsessed with factorials. He likes to calculate them, estimate them, read about them, draw them, dream about them and fight about them. He even has the value of $12!=479001600$ tattooed on his back.

He noticed a long time ago that factorials have many trailing zeroes and also wrote a program to calculate the number of trailing zeroes. For example $12!$ ends with 600, so it has 2 trailing zeroes. Now he wants to make one step further, look at the 3 digits right before the trailing zeroes. In the case of $12!$, the last 3 digits before the trailing zeroes are $016$.

-----Task-----
Given an integer $n$, find the last 3 digits before the trailing zeroes in $n!$. If there are fewer then 3 such digits, find all of them.

-----Input-----
The input contains one line with one integer $n$ ($1\leq n\leq 10000000$).

-----Output-----
Output one line with the 3 digits before trailing zeroes of $n!$. If there are fewer than 3 such digits, output all of them.

-----Examples-----
Sample Input:
5
Sample Output:
12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Fair Nut likes kvass very much. On his birthday parents presented him $n$ kegs of kvass. There are $v_i$ liters of kvass in the $i$-th keg. Each keg has a lever. You can pour your glass by exactly $1$ liter pulling this lever. The Fair Nut likes this drink very much, so he wants to pour his glass by $s$ liters of kvass. But he wants to do it, so kvass level in the least keg is as much as possible.

Help him find out how much kvass can be in the least keg or define it's not possible to pour his glass by $s$ liters of kvass.


-----Input-----

The first line contains two integers $n$ and $s$ ($1 \le n \le 10^3$, $1 \le s \le 10^{12}$) — the number of kegs and glass volume.

The second line contains $n$ integers $v_1, v_2, \ldots, v_n$ ($1 \le v_i \le 10^9$) — the volume of $i$-th keg.


-----Output-----

If the Fair Nut cannot pour his glass by $s$ liters of kvass, print $-1$. Otherwise, print a single integer — how much kvass in the least keg can be.


-----Examples-----
Input
3 3
4 3 5

Output
3

Input
3 4
5 3 4

Output
2

Input
3 7
1 2 3

Output
-1



-----Note-----

In the first example, the answer is $3$, the Fair Nut can take $1$ liter from the first keg and $2$ liters from the third keg. There are $3$ liters of kvass in each keg.

In the second example, the answer is $2$, the Fair Nut can take $3$ liters from the first keg and $1$ liter from the second keg.

In the third example, the Fair Nut can't pour his cup by $7$ liters, so the answer is $-1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For given n points in metric space, find the distance of the closest points.

Constraints

* 2 ≤ n ≤ 100,000
* -100 ≤ x, y ≤ 100

Input


n
x0 y0
x1 y1
:
xn-1 yn-1


The first integer n is the number of points.

In the following n lines, the coordinate of the i-th point is given by two real numbers xi and yi. Each value is a real number with at most 6 digits after the decimal point.

Output

Print the distance in a line. The output values should be in a decimal fraction with an error less than 0.000001.

Examples

Input

2
0.0 0.0
1.0 0.0


Output

1.000000


Input

3
0.0 0.0
2.0 0.0
1.0 1.0


Output

1.41421356237

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vladimir would like to prepare a present for his wife: they have an anniversary! He decided to buy her exactly $n$ flowers.

Vladimir went to a flower shop, and he was amazed to see that there are $m$ types of flowers being sold there, and there is unlimited supply of flowers of each type. Vladimir wants to choose flowers to maximize the happiness of his wife. He knows that after receiving the first flower of the $i$-th type happiness of his wife increases by $a_i$ and after receiving each consecutive flower of this type her happiness increases by $b_i$. That is, if among the chosen flowers there are $x_i > 0$ flowers of type $i$, his wife gets $a_i + (x_i - 1) \cdot b_i$ additional happiness (and if there are no flowers of type $i$, she gets nothing for this particular type).

Please help Vladimir to choose exactly $n$ flowers to maximize the total happiness of his wife.


-----Input-----

The first line contains the only integer $t$ ($1 \leq t \leq 10\,000$), the number of test cases. It is followed by $t$ descriptions of the test cases.

Each test case description starts with two integers $n$ and $m$ ($1 \le n \le 10^9$, $1 \le m \le 100\,000$), the number of flowers Vladimir needs to choose and the number of types of available flowers.

The following $m$ lines describe the types of flowers: each line contains integers $a_i$ and $b_i$ ($0 \le a_i, b_i \le 10^9$) for $i$-th available type of flowers.

The test cases are separated by a blank line. It is guaranteed that the sum of values $m$ among all test cases does not exceed $100\,000$.


-----Output-----

For each test case output a single integer: the maximum total happiness of Vladimir's wife after choosing exactly $n$ flowers optimally.


-----Example-----
Input
2
4 3
5 0
1 4
2 2

5 3
5 2
4 2
3 1

Output
14
16



-----Note-----

In the first example case Vladimir can pick 1 flower of the first type and 3 flowers of the second type, in this case the total happiness equals $5 + (1 + 2 \cdot 4) = 14$.

In the second example Vladimir can pick 2 flowers of the first type, 2 flowers of the second type, and 1 flower of the third type, in this case the total happiness equals $(5 + 1 \cdot 2) + (4 + 1 \cdot 2) + 3 = 16$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Cybernetics Failures (CF) organisation made a prototype of a bomb technician robot. To find the possible problems it was decided to carry out a series of tests. At the beginning of each test the robot prototype will be placed in cell (x_0, y_0) of a rectangular squared field of size x × y, after that a mine will be installed into one of the squares of the field. It is supposed to conduct exactly x·y tests, each time a mine is installed into a square that has never been used before. The starting cell of the robot always remains the same.

After placing the objects on the field the robot will have to run a sequence of commands given by string s, consisting only of characters 'L', 'R', 'U', 'D'. These commands tell the robot to move one square to the left, to the right, up or down, or stay idle if moving in the given direction is impossible. As soon as the robot fulfills all the sequence of commands, it will blow up due to a bug in the code. But if at some moment of time the robot is at the same square with the mine, it will also blow up, but not due to a bug in the code.

Moving to the left decreases coordinate y, and moving to the right increases it. Similarly, moving up decreases the x coordinate, and moving down increases it.

The tests can go on for very long, so your task is to predict their results. For each k from 0 to length(s) your task is to find in how many tests the robot will run exactly k commands before it blows up.


-----Input-----

The first line of the input contains four integers x, y, x_0, y_0 (1 ≤ x, y ≤ 500, 1 ≤ x_0 ≤ x, 1 ≤ y_0 ≤ y) — the sizes of the field and the starting coordinates of the robot. The coordinate axis X is directed downwards and axis Y is directed to the right.

The second line contains a sequence of commands s, which should be fulfilled by the robot. It has length from 1 to 100 000 characters and only consists of characters 'L', 'R', 'U', 'D'.


-----Output-----

Print the sequence consisting of (length(s) + 1) numbers. On the k-th position, starting with zero, print the number of tests where the robot will run exactly k commands before it blows up.


-----Examples-----
Input
3 4 2 2
UURDRDRL

Output
1 1 0 1 1 1 1 0 6

Input
2 2 2 2
ULD

Output
1 1 1 1



-----Note-----

In the first sample, if we exclude the probable impact of the mines, the robot's route will look like that: $(2,2) \rightarrow(1,2) \rightarrow(1,2) \rightarrow(1,3) \rightarrow(2,3) \rightarrow(2,4) \rightarrow(3,4) \rightarrow(3,4) \rightarrow(3,3)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program which manipulates a sequence A = {a0, a1, . . . , an−1} with the following operations:

* update(s, t, x): change as, as+1, ..., at to x.
* find(s, t): report the minimum element in as, as+1, ..., at.



Note that the initial values of ai (i = 0, 1, . . . , n−1) are 231-1.

Constraints

* 1 ≤ n ≤ 100000
* 1 ≤ q ≤ 100000
* 0 ≤ s ≤ t < n
* 0 ≤ x < 231−1

Input


n q
query1
query2
:
queryq


In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, ith query queryi is given in the following format:


0 s t x


or


1 s t


The first digit represents the type of the query. '0' denotes update(s, t, x) and '1' denotes find(s, t).

Output

For each find operation, print the minimum value.

Examples

Input

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


Output

1
2


Input

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


Output

2147483647
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a value N, find out the largest palindrome number which is product of two N-digit numbers.
 
Example 1:
Input: N = 2
Output: 9009
Explanation: 9009 is the largest number 
which is product of two 2-digit numbers. 
9009 = 91*99.
Example 2:
Input: N = 1
Output: 9
Explanation: 9 is the largest number 
which is product of two 1-digit numbers. 
3 * 3 = 9.
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function LargestProductPalin() which takes N as input parameter and returns largest palindromic product of 2 N-digit numbers.
 
Expected Time Complexity: O(10^{n+1})
Expected Space Complexity: O(1)
 
Constraints:
1 <= N <= 6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Function Descriptions=====
We have seen the applications of union, intersection, difference and symmetric difference operations, but these operations do not make any changes or mutations to the set.

We can use the following operations to create mutations to a set:

.update() or |=
Update the set by adding elements from an iterable/another set.

>>> H = set("Hacker")
>>> R = set("Rank")
>>> H.update(R)
>>> print H
set(['a', 'c', 'e', 'H', 'k', 'n', 'r', 'R'])

.intersection_update() or &=
Update the set by keeping only the elements found in it and an iterable/another set.

>>> H = set("Hacker")
>>> R = set("Rank")
>>> H.intersection_update(R)
>>> print H
set(['a', 'k'])

.difference_update() or -=
Update the set by removing elements found in an iterable/another set.

>>> H = set("Hacker")
>>> R = set("Rank")
>>> H.difference_update(R)
>>> print H
set(['c', 'e', 'H', 'r'])

.symmetric_difference_update() or ^=
Update the set by only keeping the elements found in either set, but not in both.

>>> H = set("Hacker")
>>> R = set("Rank")
>>> H.symmetric_difference_update(R)
>>> print H
set(['c', 'e', 'H', 'n', 'r', 'R'])

=====Problem Statement=====
You are given a set A and N number of other sets. These N number of sets have to perform some specific mutation operations on set A.

Your task is to execute those operations and print the sum of elements from set A.

=====Input Format=====
The first line contains the number of elements in set A.
The second line contains the space separated list of elements in set A.
The third line contains integer N, the number of other sets.
The next 2 * N lines are divided into N parts containing two lines each.
The first line of each part contains the space separated entries of the operation name and the length of the other set.
The second line of each part contains space separated list of elements in the other set.

=====Constraints=====
0<len(set(A))<1000
0<len(otherSets)<100
0<N<100

=====Output Format=====
Output the sum of elements in set A.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given integers N, K, and an integer sequence A of length M.

An integer sequence where each element is between 1 and K (inclusive) is said to be colorful when there exists a contiguous subsequence of length K of the sequence that contains one occurrence of each integer between 1 and K (inclusive).

For every colorful integer sequence of length N, count the number of the contiguous subsequences of that sequence which coincide with A, then find the sum of all the counts. Here, the answer can be extremely large, so find the sum modulo 10^9+7.

Constraints

* 1 \leq N \leq 25000
* 1 \leq K \leq 400
* 1 \leq M \leq N
* 1 \leq A_i \leq K
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K M
A_1 A_2 ... A_M


Output

For every colorful integer sequence of length N, count the number of the contiguous subsequences of that sequence which coincide with A, then print the sum of all the counts modulo 10^9+7.

Examples

Input

3 2 1
1


Output

9


Input

4 2 2
1 2


Output

12


Input

7 4 5
1 2 3 1 2


Output

17


Input

5 4 3
1 1 1


Output

0


Input

10 3 5
1 1 2 3 3


Output

1458


Input

25000 400 4
3 7 31 127


Output

923966268


Input

9954 310 12
267 193 278 294 6 63 86 166 157 193 168 43


Output

979180369

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