vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Problem statement

N-winged rabbit is on a balance beam of length L-1. The initial position of the i-th rabbit is the integer x_i, which satisfies 0 ≤ x_ {i} \ lt x_ {i + 1} ≤ L−1. The coordinates increase as you move to the right. Any i-th rabbit can jump to the right (ie, move from x_i to x_i + a_i) any number of times, just a distance a_i. However, you cannot jump over another rabbit or enter a position below -1 or above L. Also, at most one rabbit can jump at the same time, and at most one rabbit can exist at a certain coordinate.

How many possible states of x_ {0},…, x_ {N−1} after starting from the initial state and repeating the jump any number of times? Find by the remainder divided by 1 \, 000 \, 000 \, 007.

input

The input is given in the following format.


N L
x_ {0}… x_ {N−1}
a_ {0}… a_ {N−1}


Constraint

* All inputs are integers
* 1 \ ≤ N \ ≤ 5 \,000
* N \ ≤ L \ ≤ 5 \,000
* 0 \ ≤ x_ {i} \ lt x_ {i + 1} \ ≤ L−1
* 0 \ ≤ a_ {i} \ ≤ L−1



output

Print the answer in one line.

sample

Sample input 1


13
0
1


Sample output 1


3


If 1/0 is used to express the presence / absence of a rabbit, there are three ways: 100, 010, and 001.

Sample input 2


twenty four
0 1
1 2


Sample output 2


Four


There are four ways: 1100, 1001, 0101, 0011.

Sample input 3


10 50
0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 1


Sample output 3


272278100


The binomial coefficient C (50,10) = 10 \, 272 \, 278 \, 170, and the remainder obtained by dividing it by 1 \, 000 \, 000 \, 007 is 272 \, 278 \, 100.





Example

Input

1 3
0
1


Output

3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are a total of A + B cats and dogs.
Among them, A are known to be cats, but the remaining B are not known to be either cats or dogs.
Determine if it is possible that there are exactly X cats among these A + B animals.

-----Constraints-----
 - 1 \leq A \leq 100
 - 1 \leq B \leq 100
 - 1 \leq X \leq 200
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
A B X

-----Output-----
If it is possible that there are exactly X cats, print YES; if it is impossible, print NO.

-----Sample Input-----
3 5 4

-----Sample Output-----
YES

If there are one cat and four dogs among the B = 5 animals, there are X = 4 cats in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of integers nums and an integer K, your task is to find the smallest positive integer divisor, such that upon dividing all the elements of the given array by it, the sum of the division's result is less than or equal to the given integer K.
Each result of the division is rounded to the nearest integer greater than or equal to that element. For Example: 7/3 = 3.
Example:
Input: 
A = [1 2 5 9]
6
Output:
5
Explanation:
If the divisor is 5 the sum will be 5 (1+1+1+2), which is less than 6.
Your Task:
Complete the function int smallestDivisor(), which takes a vector nums and an integer K and returns the smallest integer as asked.
Expected Time Complexity: O(nlogn).
Expected Auxiliary Space: O(n).
Constraints:
1 <= nums.length <= 5 * 10^{5}
1 <= nums[i] <= 10^{9}
nums.length <= K <= 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have been given a positive integer N. You need to find and print the Factorial  of this number. The Factorial of a positive integer N refers to the product of all number in the range from 1 to N. You can read more about the factorial of a number here.

Input Format:
The first and only line of the input contains a single integer N denoting the number whose factorial you need to find. 

Output Format
Output a single line denoting the factorial of the number N.

Constraints
 1 ≤ N ≤ 10   

SAMPLE INPUT
2

SAMPLE OUTPUT
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A line on the plane is described by an equation Ax + By + C = 0. You are to find any point on this line, whose coordinates are integer numbers from  - 5·1018 to 5·1018 inclusive, or to find out that such points do not exist.

Input

The first line contains three integers A, B and C ( - 2·109 ≤ A, B, C ≤ 2·109) — corresponding coefficients of the line equation. It is guaranteed that A2 + B2 > 0.

Output

If the required point exists, output its coordinates, otherwise output -1.

Examples

Input

2 5 3


Output

6 -3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an image A composed of N rows and N columns of pixels, and a template image B composed of M rows and M columns of pixels.
A pixel is the smallest element of an image, and in this problem it is a square of size 1×1.
Also, the given images are binary images, and the color of each pixel is either white or black.

In the input, every pixel is represented by a character: `.` corresponds to a white pixel, and `#` corresponds to a black pixel.
The image A is given as N strings A_1,...,A_N.
The j-th character in the string A_i corresponds to the pixel at the i-th row and j-th column of the image A (1≦i,j≦N).
Similarly, the template image B is given as M strings B_1,...,B_M.
The j-th character in the string B_i corresponds to the pixel at the i-th row and j-th column of the template image B (1≦i,j≦M).

Determine whether the template image B is contained in the image A when only parallel shifts can be applied to the images.

Constraints

* 1≦M≦N≦50
* A_i is a string of length N consisting of `#` and `.`.
* B_i is a string of length M consisting of `#` and `.`.

Input

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


N M
A_1
A_2
:
A_N
B_1
B_2
:
B_M


Output

Print `Yes` if the template image B is contained in the image A. Print `No` otherwise.

Examples

Input

3 2
#.#
.#.
#.#
#.
.#


Output

Yes


Input

3 2
.#
.#.
.#
.
.#


Output

Yes


Input

4 1
....
....
....
....


Output

No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gladstone Gander is walking through Duckburg and needs to get to his date with Daisy Duck as soon as possible. If he doesn’t get there in time, Donald might show up and take his place instead. 

Duckburg has recently started providing a very eco-friendly way of public transport: bikes. At many bike stations throughout the city, one can pick up a free bike, ride it to another bike station, and drop it there. This gives Gladstone two ways of transportion: on foot or by bike. Biking is faster, of course, but he must pick up and leave the bikes at the designated stations. Gladstone can walk or bike between any two points in a straight line.

Gladstone possesses a map of the (rectangular) center of Duckburg. His current position is on this map and so is the meeting point with Daisy. The map also contains the locations of all bike stations within the boundaries of the map.

There can be way more bike stations though, that are not within the boundaries of the map. Considering his luck, you can assume that the moment Gladstone walks (or bikes) off the map, he encounters a bike station if that suits him well. The bike stations not on the map can be located anywhere outside the map, they do not have to lie on integer coordinates.

That leaves Gladstone with the task of figuring out which route to take. Can you help him out? Given the map and his infinite amount of luck, what is the fastest time to his date with Daisy?

-----Input-----
The input consists of:
 - one line with two integers $v_{\text {walk}}$ and $v_{\text {bike}}$ ($1\le v_{\text {walk}}< v_{\text {bike}} \le 1000$), the speeds of walking and of biking;
 - one line with four integers $x_1, y_1, x_2$ and $y_2$ ($-10^6\le x_1< x_2\le 10^6$; $-10^6\le y_1< y_2\le 10^6$), the bounding coordinates of the map of the center of Duckburg;
 - one line with two integers $x_{\text {G}}$ and $y_{\text {G}}$, Gladstone’s position;
 - one line with two integers $x_{\text {D}}$ and $y_{\text {D}}$, Daisy’s position;
 - one line with one integer $n$ ($0\le n\le 1000$), the number of known bike stations;
 - $n$ lines with two integers $x_{\text {station}}$ and $y_{\text {station}}$ each, the coordinates of the known bike stations.

All coordinates are on the map of the center, i.e., $x_1\le x\le x_2$ and $y_1\le y\le y_2$.

-----Output-----
Output one line with the shortest possible time for Gladstone to get to Daisy. Your answer should have an absolute or relative error of at most $10^{-6}$.

-----Examples-----
Sample Input:
1 8
0 0 10 10
5 1
5 9
3
5 8
2 2
9 6
Sample Output:
3.000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Victor adores the sets theory. Let us remind you that a set is a group of numbers where all numbers are pairwise distinct. Today Victor wants to find a set of integers S that has the following properties:

  * for all x <image> the following inequality holds l ≤ x ≤ r; 
  * 1 ≤ |S| ≤ k; 
  * lets denote the i-th element of the set S as si; value <image> must be as small as possible. 



Help Victor find the described set.

Input

The first line contains three space-separated integers l, r, k (1 ≤ l ≤ r ≤ 1012; 1 ≤ k ≤ min(106, r - l + 1)).

Output

Print the minimum possible value of f(S). Then print the cardinality of set |S|. Then print the elements of the set in any order.

If there are multiple optimal sets, you can print any of them.

Examples

Input

8 15 3


Output

1
2
10 11


Input

8 30 7


Output

0
5
14 9 28 11 16

Note

Operation <image> represents the operation of bitwise exclusive OR. In other words, it is the XOR operation.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Koko loves to eat bananas.  There are N piles of bananas, the i-th pile has piles[i] bananas.  The guards have gone and will come back in H hours.
Koko can decide her bananas-per-hour eating speed of K.  Each hour, she chooses some pile of bananas, and eats K bananas from that pile.  If the pile has less than K bananas, she eats all of them instead, and won't eat any more bananas during this hour.
Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.
Return the minimum integer K such that she can eat all the bananas within H hours.
 
Example 1:
Input: piles = [3,6,7,11], H = 8
Output: 4
Example 2:
Input: piles = [30,11,23,4,20], H = 5
Output: 30
Example 3:
Input: piles = [30,11,23,4,20], H = 6
Output: 23

 
Constraints:

1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya has an array *a* consisting of positive integer numbers. Vasya wants to divide this array into two non-empty consecutive parts (the prefix and the suffix) so that the sum of all elements in the first part equals to the sum of elements in the second part. It is not always possible, so Vasya will move some element before dividing the array (Vasya will erase some element and insert it into an arbitrary position).

Inserting an element in the same position he was erased from is also considered moving.

Can Vasya divide the array after choosing the right element to move and its new position?

Input Specification:
The first line contains single integer *n* (1<=≤<=*n*<=≤<=100000) — the size of the array.

The second line contains *n* integers *a*1,<=*a*2... *a**n* (1<=≤<=*a**i*<=≤<=109) — the elements of the array.

Output Specification:
Print YES if Vasya can divide the array after moving one element. Otherwise print NO.

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

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

Note:
In the first example Vasya can move the second element to the end of the array.

In the second example no move can make the division possible.

In the third example Vasya can move the fourth element by one position to the left.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Famous Brazil city Rio de Janeiro holds a tennis tournament and Ostap Bender doesn't want to miss this event. There will be *n* players participating, and the tournament will follow knockout rules from the very first game. That means, that if someone loses a game he leaves the tournament immediately.

Organizers are still arranging tournament grid (i.e. the order games will happen and who is going to play with whom) but they have already fixed one rule: two players can play against each other only if the number of games one of them has already played differs by no more than one from the number of games the other one has already played. Of course, both players had to win all their games in order to continue participating in the tournament.

Tournament hasn't started yet so the audience is a bit bored. Ostap decided to find out what is the maximum number of games the winner of the tournament can take part in (assuming the rule above is used). However, it is unlikely he can deal with this problem without your help.

Input Specification:
The only line of the input contains a single integer *n* (2<=≤<=*n*<=≤<=1018) — the number of players to participate in the tournament.

Output Specification:
Print the maximum number of games in which the winner of the tournament can take part.

Demo Input:
['2\n', '3\n', '4\n', '10\n']

Demo Output:
['1\n', '2\n', '2\n', '4\n']

Note:
In all samples we consider that player number 1 is the winner.

In the first sample, there would be only one game so the answer is 1.

In the second sample, player 1 can consequently beat players 2 and 3. 

In the third sample, player 1 can't play with each other player as after he plays with players 2 and 3 he can't play against player 4, as he has 0 games played, while player 1 already played 2. Thus, the answer is 2 and to achieve we make pairs (1, 2) and (3, 4) and then clash the winners.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Olya likes milk very much. She drinks k cartons of milk each day if she has at least k and drinks all of them if she doesn't. But there's an issue — expiration dates. Each carton has a date after which you can't drink it (you still can drink it exactly at the date written on the carton). Due to this, if Olya's fridge contains a carton past its expiry date, she throws it away.

Olya hates throwing out cartons, so when she drinks a carton, she chooses the one which expires the fastest. It's easy to understand that this strategy minimizes the amount of cartons thrown out and lets her avoid it if it's even possible.

<image> Milk. Best before: 20.02.2017.

The main issue Olya has is the one of buying new cartons. Currently, there are n cartons of milk in Olya's fridge, for each one an expiration date is known (how soon does it expire, measured in days). In the shop that Olya visited there are m cartons, and the expiration date is known for each of those cartons as well.

Find the maximum number of cartons Olya can buy so that she wouldn't have to throw away any cartons. Assume that Olya drank no cartons today. 

Input

In the first line there are three integers n, m, k (1 ≤ n, m ≤ 106, 1 ≤ k ≤ n + m) — the amount of cartons in Olya's fridge, the amount of cartons in the shop and the number of cartons Olya drinks each day.

In the second line there are n integers f1, f2, ..., fn (0 ≤ fi ≤ 107) — expiration dates of the cartons in Olya's fridge. The expiration date is expressed by the number of days the drinking of this carton can be delayed. For example, a 0 expiration date means it must be drunk today, 1 — no later than tomorrow, etc.

In the third line there are m integers s1, s2, ..., sm (0 ≤ si ≤ 107) — expiration dates of the cartons in the shop in a similar format.

Output

If there's no way for Olya to drink the cartons she already has in her fridge, print -1.

Otherwise, in the first line print the maximum number x of cartons which Olya can buy so that she wouldn't have to throw a carton away. The next line should contain exactly x integers — the numbers of the cartons that should be bought (cartons are numbered in an order in which they are written in the input, starting with 1). Numbers should not repeat, but can be in arbitrary order. If there are multiple correct answers, print any of them.

Examples

Input

3 6 2
1 0 1
2 0 2 0 0 2


Output

3
1 2 3

Input

3 1 2
0 0 0
1


Output

-1

Input

2 1 2
0 1
0


Output

1
1 

Note

In the first example k = 2 and Olya has three cartons with expiry dates 0, 1 and 1 (they expire today, tomorrow and tomorrow), and the shop has 3 cartons with expiry date 0 and 3 cartons with expiry date 2. Olya can buy three cartons, for example, one with the expiry date 0 and two with expiry date 2.

In the second example all three cartons Olya owns expire today and it means she would have to throw packets away regardless of whether she buys an extra one or not.

In the third example Olya would drink k = 2 cartons today (one she alreay has in her fridge and one from the shop) and the remaining one tomorrow.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Long time ago Alex created an interesting problem about parallelogram. The input data for this problem contained four integer points on the Cartesian plane, that defined the set of vertices of some non-degenerate (positive area) parallelogram. Points not necessary were given in the order of clockwise or counterclockwise traversal.

Alex had very nice test for this problem, but is somehow happened that the last line of the input was lost and now he has only three out of four points of the original parallelogram. He remembers that test was so good that he asks you to restore it given only these three points.

Input

The input consists of three lines, each containing a pair of integer coordinates xi and yi ( - 1000 ≤ xi, yi ≤ 1000). It's guaranteed that these three points do not lie on the same line and no two of them coincide.

Output

First print integer k — the number of ways to add one new integer point such that the obtained set defines some parallelogram of positive area. There is no requirement for the points to be arranged in any special order (like traversal), they just define the set of vertices.

Then print k lines, each containing a pair of integer — possible coordinates of the fourth point.

Example

Input

0 0
1 0
0 1


Output

3
1 -1
-1 1
1 1

Note

If you need clarification of what parallelogram is, please check Wikipedia page:

https://en.wikipedia.org/wiki/Parallelogram

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n lamps in a line. The lamps are numbered 1 to n from left to right. There are also n keys. When key number i is pressed, all lamps number x such that i|x change their state.

For two integer numbers a and b, we say a|b if and only if there exists an integer c such that a × c = b.

Amirali likes to play with the keys. He randomly pressed k keys and wants to know the final state of the lamps. Help him by writing a Pike piece of code to solve this task.

Input

The first line of input contains a single integer n, the number of lamps (1 ≤ n ≤ 105).

The following line contains n words. The i-th word describes the initial state of lamp number i (see samples for details).

The following line contains a single integer k (1 ≤ k ≤ 104), the number of times a key is pressed. Then in the next line come k integers in range [1, n] which are the numbers of the pressed keys.

Output

Write n words to output. Describe the final state of the lamps. See samples for more details.

Examples

Input

2
off off
2
1 2


Output

on off 


Input

3
off off on
6
1 1 1 1 2 2


Output

off off on 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nim is the most famous two-player algorithm game. The basic rules for this game are as follows:

The game starts with a number of piles of stones.  The number of stones in each pile may not be equal.
The players alternately pick up $\mbox{1}$ or more stones from $\mbox{1}$ pile
The player to remove the last stone wins.

For example, there are $n=3$ piles of stones having $pile=[3,2,4]$ stones in them.  Play may proceed as follows:

Player  Takes           Leaving
                        pile=[3,2,4]
1       2 from pile[1]  pile=[3,4]
2       2 from pile[1]  pile=[3,2]
1       1 from pile[0]  pile=[2,2]
2       1 from pile[0]  pile=[1,2]
1       1 from pile[1]  pile=[1,1]
2       1 from pile[0]  pile=[0,1]
1       1 from pile[1]  WIN

Given the value of $n$ and the number of stones in each pile, determine the game's winner if both players play optimally.

Function Desctription  

Complete the nimGame function in the editor below.  It should return a string, either First or Second.  

nimGame has the following parameter(s):  

pile: an integer array that represents the number of stones in each pile  

Input Format

The first line contains an integer, $\mathrm{~g~}$, denoting the number of games they play.

Each of the next $\mathrm{~g~}$ pairs of lines is as follows:  

The first line contains an integer $n$, the number of piles.
The next line contains $n$ space-separated integers $pile[i]$, the number of stones in each pile.

Constraints

$1\leq g\leq100$
$1\leq n\leq100$
$0\leq s_i\leq100$
Player 1 always goes first.

Output Format

For each game, print the name of the winner on a new line (i.e., either First or Second).

Sample Input
2
2
1 1
3
2 1 4

Sample Output
Second
First

Explanation

In the first case, there are $n=2$ piles of $pile=[1,1]$ stones.  Player $\mbox{1}$ has to remove one pile on the first move.  Player $2$ removes the second for a win.

In the second case, there are $n=3$ piles of $pile=[2,1,4]$ stones.  If player $\mbox{1}$ removes any one pile, player $2$ can remove all but one of another pile and force a win.  If player $\mbox{1}$ removes less than a pile, in any case, player $2$ can force a win as well, given optimal play.

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