vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Andryusha and Socks

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Andryusha is an orderly boy and likes to keep things in their place.

Today he faced a problem to put his socks in the wardrobe. He has *n* distinct pairs of socks which are initially in a bag. The pairs are numbered from 1 to *n*. Andryusha wants to put paired socks together and put them in the wardrobe. He takes the socks one by one from the bag, and for each sock he looks whether the pair of this sock has been already took out of the bag, or not. If not (that means the pair of this sock is still in the bag), he puts the current socks on the table in front of him. Otherwise, he puts both socks from the pair to the wardrobe.

Andryusha remembers the order in which he took the socks from the bag. Can you tell him what is the maximum number of socks that were on the table at the same time?

Input Specification:
The first line contains the single integer *n* (1<=≤<=*n*<=≤<=105) — the number of sock pairs.

The second line contains 2*n* integers *x*1,<=*x*2,<=...,<=*x*2*n* (1<=≤<=*x**i*<=≤<=*n*), which describe the order in which Andryusha took the socks from the bag. More precisely, *x**i* means that the *i*-th sock Andryusha took out was from pair *x**i*.

It is guaranteed that Andryusha took exactly two socks of each pair.

Output Specification:
Print single integer — the maximum number of socks that were on the table at the same time.

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

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

Note:
In the first example Andryusha took a sock from the first pair and put it on the table. Then he took the next sock which is from the first pair as well, so he immediately puts both socks to the wardrobe. Thus, at most one sock was on the table at the same time.

In the second example Andryusha behaved as follows: 
 -  Initially the table was empty, he took out a sock from pair 2 and put it on the table. -  Sock (2) was on the table. Andryusha took out a sock from pair 1 and put it on the table. -  Socks (1, 2) were on the table. Andryusha took out a sock from pair 1, and put this pair into the wardrobe. -  Sock (2) was on the table. Andryusha took out a sock from pair 3 and put it on the table. -  Socks (2, 3) were on the table. Andryusha took out a sock from pair 2, and put this pair into the wardrobe. -  Sock (3) was on the table. Andryusha took out a sock from pair 3 and put this pair into the wardrobe.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between the easy and the hard versions is constraints.

A subsequence is a string that can be derived from another string by deleting some or no symbols without changing the order of the remaining symbols. Characters to be deleted are not required to go successively, there can be any gaps between them. For example, for the string "abaca" the following strings are subsequences: "abaca", "aba", "aaa", "a" and "" (empty string). But the following strings are not subsequences: "aabaca", "cb" and "bcaa".

You are given a string $s$ consisting of $n$ lowercase Latin letters.

In one move you can take any subsequence $t$ of the given string and add it to the set $S$. The set $S$ can't contain duplicates. This move costs $n - |t|$, where $|t|$ is the length of the added subsequence (i.e. the price equals to the number of the deleted characters).

Your task is to find out the minimum possible total cost to obtain a set $S$ of size $k$ or report that it is impossible to do so.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 100, 1 \le k \le 10^{12}$) — the length of the string and the size of the set, correspondingly.

The second line of the input contains a string $s$ consisting of $n$ lowercase Latin letters.


-----Output-----

Print one integer — if it is impossible to obtain the set $S$ of size $k$, print -1. Otherwise, print the minimum possible total cost to do it.


-----Examples-----
Input
4 5
asdf

Output
4

Input
5 6
aaaaa

Output
15

Input
5 7
aaaaa

Output
-1

Input
10 100
ajihiushda

Output
233



-----Note-----

In the first example we can generate $S$ = { "asdf", "asd", "adf", "asf", "sdf" }. The cost of the first element in $S$ is $0$ and the cost of the others is $1$. So the total cost of $S$ is $4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Artem is a very smart programmer. He knows many different difficult algorithms. Recently he has mastered in 2-SAT one.

In computer science, 2-satisfiability (abbreviated as 2-SAT) is the special case of the problem of determining whether a conjunction (logical AND) of disjunctions (logical OR) have a solution, in which all disjunctions consist of no more than two arguments (variables). For the purpose of this problem we consider only 2-SAT formulas where each disjunction consists of exactly two arguments.

Consider the following 2-SAT problem as an example: <image>. Note that there might be negations in 2-SAT formula (like for x1 and for x4).

Artem now tries to solve as many problems with 2-SAT as possible. He found a very interesting one, which he can not solve yet. Of course, he asks you to help him. 

The problem is: given two 2-SAT formulas f and g, determine whether their sets of possible solutions are the same. Otherwise, find any variables assignment x such that f(x) ≠ g(x). 

Input

The first line of the input contains three integers n, m1 and m2 (1 ≤ n ≤ 1000, 1 ≤ m1, m2 ≤ n2) — the number of variables, the number of disjunctions in the first formula and the number of disjunctions in the second formula, respectively.

Next m1 lines contains the description of 2-SAT formula f. The description consists of exactly m1 pairs of integers xi ( - n ≤ xi ≤ n, xi ≠ 0) each on separate line, where xi > 0 corresponds to the variable without negation, while xi < 0 corresponds to the variable with negation. Each pair gives a single disjunction. Next m2 lines contains formula g in the similar format.

Output

If both formulas share the same set of solutions, output a single word "SIMILAR" (without quotes). Otherwise output exactly n integers xi (<image>) — any set of values x such that f(x) ≠ g(x).

Examples

Input

2 1 1
1 2
1 2


Output

SIMILAR


Input

2 1 1
1 2
1 -2


Output

0 0 

Note

First sample has two equal formulas, so they are similar by definition.

In second sample if we compute first function with x1 = 0 and x2 = 0 we get the result 0, because <image>. But the second formula is 1, because <image>.

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.
You have decided to give an allowance to your child depending on the outcome of the game that he will play now.
The game is played as follows:
 - There are three "integer panels", each with a digit between 1 and 9 (inclusive) printed on it, and one "operator panel" with a + printed on it.
 - The player should construct a formula of the form X + Y, by arranging the four panels from left to right. (The operator panel should not be placed at either end of the formula.)
 - Then, the amount of the allowance will be equal to the resulting value of the formula.
Given the values A, B and C printed on the integer panels used in the game, find the maximum possible amount of the allowance.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq A, B, C \leq 9

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

-----Output-----
Print the maximum possible amount of the allowance.

-----Sample Input-----
1 5 2

-----Sample Output-----
53

The amount of the allowance will be 53 when the panels are arranged as 52+1, and this is the maximum possible amount.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hideyo has come by two aerial photos of the same scale and orientation. You can see various types of buildings, but some areas are hidden by clouds. Apparently, they are of the same area, and the area covered by the second photograph falls entirely within the first. However, because they were taken at different time points, different shapes and distribution of clouds obscure identification where the area in the second photograph is located in the first. There may even be more than one area within the first that the second fits equally well.

A set of pixel information is given for each of the photographs. Write a program to extract candidate sub-areas within the first photograph that compare with the second equally well and output the number of the candidates.



Input

The input is given in the following format.


AW AH BW BH
arow1
arow2
:
arowAH
brow1
brow2
:
browBH


The first line provides the number of pixels in the horizontal and the vertical direction AW (1 ≤ AW ≤ 800) and AH (1 ≤ AH ≤ 800) for the first photograph, followed by those for the second BW (1 ≤ BW ≤ 100) and BH (1 ≤ BH ≤ 100) (AW ≥ BW andAH ≥ BH). Each of the subsequent AH lines provides pixel information (arowi) of the i-th row from the top of the first photograph. Each of the BH lines that follows provides pixel information (browi) of the i-th row from the top of the second photograph.

Each of the pixel information arowi and browi is a string of length AW and BW, respectively, consisting of upper/lower-case letters, numeric characters, or "?". Each one character represents a pixel, whereby upper/lower-case letters and numeric characters represent a type of building, and "?" indicates a cloud-covered area.

Output

Output the number of the candidates.

Examples

Input

5 5 3 3
AF??z
W?p88
???Hk
pU?m?
F???c
F??
p?8
?H?


Output

4


Input

6 5 4 2
aaaaaa
aaaaaa
aaaaaa
aaaaaa
aaaaaa
aaaa
aaaa


Output

12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are b blocks of digits. Each one consisting of the same n digits, which are given to you in the input. Wet Shark must choose exactly one digit from each block and concatenate all of those digits together to form one large integer. For example, if he chooses digit 1 from the first block and digit 2 from the second block, he gets the integer 12. 

Wet Shark then takes this number modulo x. Please, tell him how many ways he can choose one digit from each block so that he gets exactly k as the final result. As this number may be too large, print it modulo 10^9 + 7.

Note, that the number of ways to choose some digit in the block is equal to the number of it's occurrences. For example, there are 3 ways to choose digit 5 from block 3 5 6 7 8 9 5 1 1 1 1 5.


-----Input-----

The first line of the input contains four space-separated integers, n, b, k and x (2 ≤ n ≤ 50 000, 1 ≤ b ≤ 10^9, 0 ≤ k < x ≤ 100, x ≥ 2) — the number of digits in one block, the number of blocks, interesting remainder modulo x and modulo x itself.

The next line contains n space separated integers a_{i} (1 ≤ a_{i} ≤ 9), that give the digits contained in each block.


-----Output-----

Print the number of ways to pick exactly one digit from each blocks, such that the resulting integer equals k modulo x.


-----Examples-----
Input
12 1 5 10
3 5 6 7 8 9 5 1 1 1 1 5

Output
3

Input
3 2 1 2
6 2 2

Output
0

Input
3 2 1 2
3 1 2

Output
6



-----Note-----

In the second sample possible integers are 22, 26, 62 and 66. None of them gives the remainder 1 modulo 2.

In the third sample integers 11, 13, 21, 23, 31 and 33 have remainder 1 modulo 2. There is exactly one way to obtain each of these integers, so the total answer is 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kefa wants to celebrate his first big salary by going to restaurant. However, he needs company. 

Kefa has n friends, each friend will agree to go to the restaurant if Kefa asks. Each friend is characterized by the amount of money he has and the friendship factor in respect to Kefa. The parrot doesn't want any friend to feel poor compared to somebody else in the company (Kefa doesn't count). A friend feels poor if in the company there is someone who has at least d units of money more than he does. Also, Kefa wants the total friendship factor of the members of the company to be maximum. Help him invite an optimal company!


-----Input-----

The first line of the input contains two space-separated integers, n and d (1 ≤ n ≤ 10^5, $1 \leq d \leq 10^{9}$) — the number of Kefa's friends and the minimum difference between the amount of money in order to feel poor, respectively.

Next n lines contain the descriptions of Kefa's friends, the (i + 1)-th line contains the description of the i-th friend of type m_{i}, s_{i} (0 ≤ m_{i}, s_{i} ≤ 10^9) — the amount of money and the friendship factor, respectively. 


-----Output-----

Print the maximum total friendship factir that can be reached.


-----Examples-----
Input
4 5
75 5
0 100
150 20
75 1

Output
100

Input
5 100
0 7
11 32
99 10
46 8
87 54

Output
111



-----Note-----

In the first sample test the most profitable strategy is to form a company from only the second friend. At all other variants the total degree of friendship will be worse.

In the second sample test we can take all the friends.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array consisting of n integers which denote the position of a stall. You are also given an integer k which denotes the number of aggressive cows. You are given the task of assigning stalls to k cows such that the minimum distance between any two of them is the maximum possible.
The first line of input contains two space-separated integers n and k.
The second line contains n space-separated integers denoting the position of the stalls.
Example 1:
Input:
n=5 
k=3
stalls = [1 2 4 8 9]
Output:
3
Explanation:
The first cow can be placed at stalls[0], 
the second cow can be placed at stalls[2] and 
the third cow can be placed at stalls[3]. 
The minimum distance between cows, in this case, is 3, 
which also is the largest among all possible ways.
Example 2:
Input:
n=5 
k=3
stalls = [10 1 2 7 5]
Output:
4
Explanation:
The first cow can be placed at stalls[0],
the second cow can be placed at stalls[1] and
the third cow can be placed at stalls[4].
The minimum distance between cows, in this case, is 4,
which also is the largest among all possible ways.
Your Task:
Complete the function int solve(), which takes integer n, k, and a vector stalls with n integers as input and returns the largest possible minimum distance between cows.
Expected Time Complexity: O(n*log(10^9)).
Expected Auxiliary Space: O(1).
Constraints:
2 <= n <= 10^5
2 <= k <= n
0 <= stalls[i] <= 10^9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hansa did not have enough money to pay the bill of the party. Now she loves cupcakes (and can also eat any amount of it apparently), so she came up with a cupcake challenge. She challenges t people individually every time for the challenge.  The task is as follows:

Given 3 baskets filled with known amount of cupcakes in each, turn-by-turn, both the competitors have to eat at least one cupcake to at most all the cupcakes from any one basket. The one, who eats the last cupcake of all, is the winner and the other person has to pay the entire bill of the party. All the competitors, including Hansa, will play optimally. Now as Hansa is the birthday girl, she always takes the first turn. Tell us who wins each challenge.

Input:
The first line contains a single positive integer, T. T test cases follow. Each of the next T lines contain 3 space-separated integers “a b c” denoting the number of cupcakes in each basket.

Output:
A single line for each test case telling if Hansa has to pay the bill or not. If she loses the game then print “BILL” otherwise print “NO BILL”.

Constraints:
1 ≤ t ≤ 100
1 ≤ a, b, c ≤ 10^6

Problem Setter: Chintan Shah

SAMPLE INPUT
2
1 1 1
1 2 3

SAMPLE OUTPUT
NO BILL
BILL

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya recieved a gift of a string *s* with length up to 105 characters for his birthday. He took two more empty strings *t* and *u* and decided to play a game. This game has two possible moves:
 -  Extract the first character of *s* and append *t* with this character. -  Extract the last character of *t* and append *u* with this character. 
Petya wants to get strings *s* and *t* empty and string *u* lexicographically minimal.

You should write a program that will help Petya win the game.

Input Specification:
First line contains non-empty string *s* (1<=≤<=|*s*|<=≤<=105), consisting of lowercase English letters.

Output Specification:
Print resulting string *u*.

Demo Input:
['cab\n', 'acdb\n']

Demo Output:
['abc\n', 'abdc\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp has three sisters: Alice, Barbara, and Cerene. They're collecting coins. Currently, Alice has a coins, Barbara has b coins and Cerene has c coins. Recently Polycarp has returned from the trip around the world and brought n coins.

He wants to distribute all these n coins between his sisters in such a way that the number of coins Alice has is equal to the number of coins Barbara has and is equal to the number of coins Cerene has. In other words, if Polycarp gives A coins to Alice, B coins to Barbara and C coins to Cerene (A+B+C=n), then a + A = b + B = c + C.

Note that A, B or C (the number of coins Polycarp gives to Alice, Barbara and Cerene correspondingly) can be 0.

Your task is to find out if it is possible to distribute all n coins between sisters in a way described above.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases.

The next t lines describe test cases. Each test case is given on a new line and consists of four space-separated integers a, b, c and n (1 ≤ a, b, c, n ≤ 10^8) — the number of coins Alice has, the number of coins Barbara has, the number of coins Cerene has and the number of coins Polycarp has.

Output

For each test case, print "YES" if Polycarp can distribute all n coins between his sisters and "NO" otherwise.

Example

Input


5
5 3 2 8
100 101 102 105
3 2 1 100000000
10 20 15 14
101 101 101 3


Output


YES
YES
NO
NO
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The preferred way to generate user login in Polygon is to concatenate a prefix of the user's first name and a prefix of their last name, in that order. Each prefix must be non-empty, and any of the prefixes can be the full name. Typically there are multiple possible logins for each person.

You are given the first and the last name of a user. Return the alphabetically earliest login they can get (regardless of other potential Polygon users).

As a reminder, a prefix of a string s is its substring which occurs at the beginning of s: "a", "ab", "abc" etc. are prefixes of string "{abcdef}" but "b" and 'bc" are not. A string a is alphabetically earlier than a string b, if a is a prefix of b, or a and b coincide up to some position, and then a has a letter that is alphabetically earlier than the corresponding letter in b: "a" and "ab" are alphabetically earlier than "ac" but "b" and "ba" are alphabetically later than "ac".


-----Input-----

The input consists of a single line containing two space-separated strings: the first and the last names. Each character of each string is a lowercase English letter. The length of each string is between 1 and 10, inclusive. 


-----Output-----

Output a single string — alphabetically earliest possible login formed from these names. The output should be given in lowercase as well.


-----Examples-----
Input
harry potter

Output
hap

Input
tom riddle

Output
tomr

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gerald bought two very rare paintings at the Sotheby's auction and he now wants to hang them on the wall. For that he bought a special board to attach it to the wall and place the paintings on the board. The board has shape of an a1 × b1 rectangle, the paintings have shape of a a2 × b2 and a3 × b3 rectangles.

Since the paintings are painted in the style of abstract art, it does not matter exactly how they will be rotated, but still, one side of both the board, and each of the paintings must be parallel to the floor. The paintings can touch each other and the edges of the board, but can not overlap or go beyond the edge of the board. Gerald asks whether it is possible to place the paintings on the board, or is the board he bought not large enough?

Input

The first line contains two space-separated numbers a1 and b1 — the sides of the board. Next two lines contain numbers a2, b2, a3 and b3 — the sides of the paintings. All numbers ai, bi in the input are integers and fit into the range from 1 to 1000.

Output

If the paintings can be placed on the wall, print "YES" (without the quotes), and if they cannot, print "NO" (without the quotes).

Examples

Input

3 2
1 3
2 1


Output

YES


Input

5 5
3 3
3 3


Output

NO


Input

4 2
2 3
1 2


Output

YES

Note

That's how we can place the pictures in the first test:

<image>

And that's how we can do it in the third one.

<image>

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