vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Indian National Olympiad in Informatics 2012
You are given a table with 2 rows and N columns. Each cell has an integer in it. The score of such a table is defined as follows: for each column, consider the sum of the two numbers in the column; the maximum of the N numbers so obtained is the score. For example, for the table
7162
1234

the score is max(7 + 1, 1 + 2, 6 + 3, 2 + 4) = 9.

The first row of the table is fixed, and given as input. N possible ways to fill the second row are considered:
1,2,...,N
2,3,...,N,1
3,4,...,N,1,2
···
N, 1, ... , ,N − 1

For instance, for the example above, we would consider each of the following as possibilities for the second row.
1234
2341
3412
4123

Your task is to find the score for each of the above choices of the second row. In the example above, you would evaluate the following four tables,
7162 7162 7162 7162
1234 2341 3412 4123

and compute scores 9, 10, 10 and 11, respectively.

-----Input format -----
The first line of the input has a single integer, N. The second line of the input has N integers, representing the first row, from left to right.

-----Output format -----
The output should consist of a single line with N integers. For 1 ² k ² N, the kth number in the output should be the score when the second row of the table is taken to be k,k+1,...,N,1,...,k−1.

-----Test Data -----
The testdata is grouped into two subtasks with the following constraints on the inputs.
• Subtask 1 [30 points] : 1 ≤ N ≤ 3000.
• Subtask 2 [70 points] : 1 ≤ N ≤ 200000.
In both the subtasks, all the integers in the first row of the table are between 1 and 100000, inclusive.

-----Example -----
Here is the sample input and output corresponding to the example above.

-----Sample input -----
4
7 1 6 2

-----Sample output-----
9 10 10 11

Note: Your program should not print anything other than what is specified in the output format. Please remove all diagnostic print statements before making your final submission. A program with extraneous output will be treated as incorrect!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Create the function ```consecutive(arr)``` that takes an array of integers and return the minimum number of integers needed to make the contents of ```arr``` consecutive from the lowest number to the highest number.
For example:  If ```arr``` contains [4, 8, 6] then the output should be 2 because two numbers need to be added to the array (5 and 7) to make it a consecutive array of numbers from 4 to 8. Numbers in ```arr``` will be unique.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a$ consisting of $n$ integers. Beauty of array is the maximum sum of some consecutive subarray of this array (this subarray may be empty). For example, the beauty of the array [10, -5, 10, -4, 1] is 15, and the beauty of the array [-3, -5, -1] is 0.

You may choose at most one consecutive subarray of $a$ and multiply all values contained in this subarray by $x$. You want to maximize the beauty of array after applying at most one such operation.


-----Input-----

The first line contains two integers $n$ and $x$ ($1 \le n \le 3 \cdot 10^5, -100 \le x \le 100$) — the length of array $a$ and the integer $x$ respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$) — the array $a$.


-----Output-----

Print one integer — the maximum possible beauty of array $a$ after multiplying all values belonging to some consecutive subarray $x$.


-----Examples-----
Input
5 -2
-3 8 -2 1 -6

Output
22

Input
12 -3
1 3 3 7 1 3 3 7 1 3 3 7

Output
42

Input
5 10
-1 -2 -3 -4 -5

Output
0



-----Note-----

In the first test case we need to multiply the subarray [-2, 1, -6], and the array becomes [-3, 8, 4, -2, 12] with beauty 22 ([-3, 8, 4, -2, 12]).

In the second test case we don't need to multiply any subarray at all.

In the third test case no matter which subarray we multiply, the beauty of array will be equal to 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a number N. Find the total count of set bits for all numbers from 1 to N(both inclusive).
Example 1:
Input: N = 4
Output: 5
Explanation:
For numbers from 1 to 4.
For 1: 0 0 1 = 1 set bits
For 2: 0 1 0 = 1 set bits
For 3: 0 1 1 = 2 set bits
For 4: 1 0 0 = 1 set bits
Therefore, the total set bits is 5.
Example 2:
Input: N = 17
Output: 35
Explanation: From numbers 1 to 17(both inclusive), 
the total number of set bits is 35.
Your Task: The task is to complete the function countSetBits() that takes n as a parameter and returns the count of all bits.
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{8}

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

For simplicity, we'll assume that there are only three types of grapes: green grapes, purple grapes and black grapes.

Andrew, Dmitry and Michal are all grapes' lovers, however their preferences of grapes are different. To make all of them happy, the following should happen: Andrew, Dmitry and Michal should eat at least $x$, $y$ and $z$ grapes, respectively. Andrew has an extreme affinity for green grapes, thus he will eat green grapes and green grapes only. On the other hand, Dmitry is not a fan of black grapes — any types of grapes except black would do for him. In other words, Dmitry can eat green and purple grapes. Michal has a common taste — he enjoys grapes in general and will be pleased with any types of grapes, as long as the quantity is sufficient.

Knowing that his friends are so fond of grapes, Aki decided to host a grape party with them. He has prepared a box with $a$ green grapes, $b$ purple grapes and $c$ black grapes.

However, Aki isn't sure if the box he prepared contains enough grapes to make everyone happy. Can you please find out whether it's possible to distribute grapes so that everyone is happy or Aki has to buy some more grapes?

It is not required to distribute all the grapes, so it's possible that some of them will remain unused.


-----Input-----

The first line contains three integers $x$, $y$ and $z$ ($1 \le x, y, z \le 10^5$) — the number of grapes Andrew, Dmitry and Michal want to eat.

The second line contains three integers $a$, $b$, $c$ ($1 \le a, b, c \le 10^5$) — the number of green, purple and black grapes in the box.


-----Output-----

If there is a grape distribution that allows everyone to be happy, print "YES", otherwise print "NO".


-----Examples-----
Input
1 6 2
4 3 3

Output
YES

Input
5 1 1
4 3 2

Output
NO



-----Note-----

In the first example, there is only one possible distribution:

Andrew should take $1$ green grape, Dmitry should take $3$ remaining green grapes and $3$ purple grapes, and Michal will take $2$ out of $3$ available black grapes.

In the second test, there is no possible distribution, since Andrew is not be able to eat enough green grapes. :(

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Chanek is currently participating in a science fair that is popular in town. He finds an exciting puzzle in the fair and wants to solve it.

There are $N$ atoms numbered from $1$ to $N$. These atoms are especially quirky. Initially, each atom is in normal state. Each atom can be in an excited. Exciting atom $i$ requires $D_i$ energy. When atom $i$ is excited, it will give $A_i$ energy. You can excite any number of atoms (including zero).

These atoms also form a peculiar one-way bond. For each $i$, $(1 \le i < N)$, if atom $i$ is excited, atom $E_i$ will also be excited at no cost. Initially, $E_i$ = $i+1$. Note that atom $N$ cannot form a bond to any atom.

Mr. Chanek must change exactly $K$ bonds. Exactly $K$ times, Mr. Chanek chooses an atom $i$, $(1 \le i < N)$ and changes $E_i$ to a different value other than $i$ and the current $E_i$. Note that an atom's bond can remain unchanged or changed more than once. Help Mr. Chanek determine the maximum energy that he can achieve!

note: You must first change exactly $K$ bonds before you can start exciting atoms.


-----Input-----

The first line contains two integers $N$ $K$ $(4 \le N \le 10^5, 0 \le K < N)$, the number of atoms, and the number of bonds that must be changed.

The second line contains $N$ integers $A_i$ $(1 \le A_i \le 10^6)$, which denotes the energy given by atom $i$ when on excited state.

The third line contains $N$ integers $D_i$ $(1 \le D_i \le 10^6)$, which denotes the energy needed to excite atom $i$.


-----Output-----

A line with an integer that denotes the maximum number of energy that Mr. Chanek can get.


-----Example-----
Input
6 1
5 6 7 8 10 2
3 5 6 7 1 10

Output
35



-----Note-----

An optimal solution to change $E_5$ to 1 and then excite atom 5 with energy 1. It will cause atoms 1, 2, 3, 4, 5 be excited. The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10) - 1 = 35.

Another possible way is to change $E_3$ to 1 and then exciting atom 3 (which will excite atom 1, 2, 3) and exciting atom 4 (which will excite atom 4, 5, 6). The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10 + 2) - (6 + 7) = 25 which is not optimal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a matrix of integers $A$ with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$). Each element of this matrix is either $0$ or $1$.
A move consists of the following steps:
- Choose two different rows $r_1$ and $r_2$ or two different columns $c_1$ and $c_2$.
- Apply the bitwise OR operation with the second row/column on the first row/column. Formally, if you chose two rows, this means you should change $A_{r_1, k}$ to $A_{r_1, k} \lor A_{r_2, k}$ for each $1 \le k \le M$; if you chose two columns, then you should change $A_{k, c_1}$ to $A_{k, c_1} \lor A_{k, c_2}$ for each $1 \le k \le N$.
For each element of the matrix, compute the minimum number of moves required to make it equal to $1$ or determine that it is impossible. Note that these answers are independent, i.e. we are starting with the initial matrix for each of them.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $M$.
- $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$-th of these lines contains $M$ integers $A_{i, 1}, A_{i, 2}, \dots, A_{i, M}$ NOT separated by spaces.

-----Output-----
For each test case, print $N$ lines. For each valid $i$, the $i$-th of these lines should contain $M$ space-separated integers; for each valid $j$, the $j$-th of these integers should be the minimum number of moves required to make $A_{i, j}$ equal to $1$, or $-1$ if it is impossible.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N, M \le 1,000$
- $A_{i, j} \in \{0, 1\}$ for each valid $i, j$
- the sum of $N \cdot M$ for all test cases does not exceed $1,000,000$

-----Example Input-----
1
3 3
010
000
001

-----Example Output-----
1 0 1
2 1 1
1 1 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Iahub wants to meet his girlfriend Iahubina. They both live in Ox axis (the horizontal axis). Iahub lives at point 0 and Iahubina at point d.

Iahub has n positive integers a1, a2, ..., an. The sum of those numbers is d. Suppose p1, p2, ..., pn is a permutation of {1, 2, ..., n}. Then, let b1 = ap1, b2 = ap2 and so on. The array b is called a "route". There are n! different routes, one for each permutation p.

Iahub's travel schedule is: he walks b1 steps on Ox axis, then he makes a break in point b1. Then, he walks b2 more steps on Ox axis and makes a break in point b1 + b2. Similarly, at j-th (1 ≤ j ≤ n) time he walks bj more steps on Ox axis and makes a break in point b1 + b2 + ... + bj.

Iahub is very superstitious and has k integers which give him bad luck. He calls a route "good" if he never makes a break in a point corresponding to one of those k numbers. For his own curiosity, answer how many good routes he can make, modulo 1000000007 (109 + 7). 

Input

The first line contains an integer n (1 ≤ n ≤ 24). The following line contains n integers: a1, a2, ..., an (1 ≤ ai ≤ 109). 

The third line contains integer k (0 ≤ k ≤ 2). The fourth line contains k positive integers, representing the numbers that give Iahub bad luck. Each of these numbers does not exceed 109.

Output

Output a single integer — the answer of Iahub's dilemma modulo 1000000007 (109 + 7). 

Examples

Input

3
2 3 5
2
5 7


Output

1


Input

3
2 2 2
2
1 3


Output

6

Note

In the first case consider six possible orderings:

  * [2, 3, 5]. Iahub will stop at position 2, 5 and 10. Among them, 5 is bad luck for him. 
  * [2, 5, 3]. Iahub will stop at position 2, 7 and 10. Among them, 7 is bad luck for him. 
  * [3, 2, 5]. He will stop at the unlucky 5. 
  * [3, 5, 2]. This is a valid ordering. 
  * [5, 2, 3]. He got unlucky twice (5 and 7). 
  * [5, 3, 2]. Iahub would reject, as it sends him to position 5. 



In the second case, note that it is possible that two different ways have the identical set of stopping. In fact, all six possible ways have the same stops: [2, 4, 6], so there's no bad luck for Iahub.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a game called "I Wanna Be the Guy", consisting of n levels. Little X and his friend Little Y are addicted to the game. Each of them wants to pass the whole game.

Little X can pass only p levels of the game. And Little Y can pass only q levels of the game. You are given the indices of levels Little X can pass and the indices of levels Little Y can pass. Will Little X and Little Y pass the whole game, if they cooperate each other?


-----Input-----

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

The next line contains an integer p (0 ≤ p ≤ n) at first, then follows p distinct integers a_1, a_2, ..., a_{p} (1 ≤ a_{i} ≤ n). These integers denote the indices of levels Little X can pass. The next line contains the levels Little Y can pass in the same format. It's assumed that levels are numbered from 1 to n.


-----Output-----

If they can pass all the levels, print "I become the guy.". If it's impossible, print "Oh, my keyboard!" (without the quotes).


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

Output
I become the guy.

Input
4
3 1 2 3
2 2 3

Output
Oh, my keyboard!



-----Note-----

In the first sample, Little X can pass levels [1 2 3], and Little Y can pass level [2 4], so they can pass all the levels both.

In the second sample, no one can pass level 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation is a sequence of integers p1, p2, ..., pn, consisting of n distinct positive integers, each of them doesn't exceed n. Let's denote the i-th element of permutation p as pi. We'll call number n the size of permutation p1, p2, ..., pn.

Nickolas adores permutations. He likes some permutations more than the others. He calls such permutations perfect. A perfect permutation is such permutation p that for any i (1 ≤ i ≤ n) (n is the permutation size) the following equations hold ppi = i and pi ≠ i. Nickolas asks you to print any perfect permutation of size n for the given n.

Input

A single line contains a single integer n (1 ≤ n ≤ 100) — the permutation size.

Output

If a perfect permutation of size n doesn't exist, print a single integer -1. Otherwise print n distinct integers from 1 to n, p1, p2, ..., pn — permutation p, that is perfect. Separate printed numbers by whitespaces.

Examples

Input

1


Output

-1


Input

2


Output

2 1 


Input

4


Output

2 1 4 3 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pirates have notorious difficulty with enunciating. They tend to blur all the letters together and scream at people.

At long last, we need a way to unscramble what these pirates are saying.

Write a function that will accept a jumble of letters as well as a dictionary, and output a list of words that the pirate might have meant.

For example:
```
grabscrab( "ortsp", ["sport", "parrot", "ports", "matey"] )
```

Should return `["sport", "ports"]`.

Return matches in the same order as in the dictionary. Return an empty array if there are no matches.

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sevenkplus has a rooted tree with $N$ vertices. The vertices are labeled from $1$ to $N$. $1$ is the root of the tree. Each vertex $v$ has a weight $W_v$. 

He forms a $N\times N$ matrix ${M}$ from the tree. ${M}$ is defined by 

$M(x,y)=W_{lca(x,y)}$ 

where $lca(x,y)$ is the lowest common ancestor of vertex ${x}$ and vertex $y$. 

He wants to calculate the determinant of ${M}$.  

Input Format 

First line contains the number of vertices, $N$. 

Second line contains $N$ numbers, $W_1\:W_2\:\cdots\:W_N$ separated by a space. 

This is followed by $N-1$ lines. Each line contains two numbers ${x}$, $y$, denoting that there is an edge between ${x}$  and $y$.  

Output Format 

Output one line, the determinant of ${M}$ modulo $(10^9+7)$.

Constraints 

$1\leq N\leq10^5$ 

$\forall i,0\leq W_i\leq10^9$. 

Sample Input

3
1 2 3
1 2
1 3

Sample Output

2

Explanation

$M=\begin{bmatrix}1&1&1\\ 1&2&1\\ 1&1&3\end{bmatrix}$

Then, $|M|=1\times\begin{bmatrix}2&1\\ 1&3\end{bmatrix}-1\times\begin{bmatrix}1&1\\ 1&3\end{bmatrix}+1\times\begin{bmatrix}1&2\\ 1&1\end{bmatrix}$. 

Hence $|M|=(1\times5)-(1\times2)+(1\times-1)=2$

Timelimits 

Timelimits for this challenge is given here

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are organizing a cycling race on the streets of the city. The city contains n junctions, some pairs of them are connected by roads; on each road you can move in any direction. No two roads connect the same pair of intersections, and no road connects the intersection with itself.

You want the race to be open to both professional athletes and beginner cyclists, and that's why you will organize the race in three nominations: easy, moderate and difficult; each participant will choose the more suitable nomination. For each nomination you must choose the route — the chain of junctions, consecutively connected by roads. Routes must meet the following conditions:

  * all three routes should start at the same intersection, and finish at the same intersection (place of start and finish can't be the same);
  * to avoid collisions, no two routes can have common junctions (except for the common start and finish), and can not go along the same road (irrespective of the driving direction on the road for those two routes);
  * no route must pass twice through the same intersection or visit the same road twice (irrespective of the driving direction on the road for the first and second time of visit).



Preparing for the competition is about to begin, and you need to determine the routes of the race as quickly as possible. The length of the routes is not important, it is only important that all the given requirements were met.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 2·105) — the number of intersections and roads, respectively.

The following m lines contain two integers — the numbers of the intersections connected by a road (the intersections are numbered starting with 1). It is guaranteed that each pair of intersections is connected by no more than one road, and no road connects the intersection to itself.

Please note that it is not guaranteed that you can get from any junction to any other one by using the roads.

Output

If it is possible to create the routes, in the first line print "YES". In the next three lines print the descriptions of each of the three routes in the format "l p1 ... pl", where l is the number of intersections in the route, and p1, ..., pl are their numbers in the order they follow. The routes must meet all the requirements specified in the statement.

If it is impossible to make the routes in accordance with the requirements, print NO.

Examples

Input

4 4
1 2
2 3
3 4
4 1


Output

NO


Input

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


Output

YES
3 5 4 1
3 5 3 1
3 5 2 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A Train started its journey at x=-infinity is travelling on the x-Coordinate Axis. Given n passengers and the coordinates $b_i$ and $d_i$ for each of the $ith$ passenger at which they board and leave from the train respectively. Due to current COVID-19 crisis, the train is monitored at each mile/coordinate. The infection degree of the train at each mile is equal to the total passengers present in the train at that mile/coordinate. The train stops its journey if no more passengers are there to board the train. The term infection severity of the journey is defined as the sum of infection degrees noted at each mile. Find the Infection severity of the journey. Note: A passenger is considered for calculation of infection degree at both boarding and leaving stations.

Since the answer can be very large, print it modulo $(10^9)+7$.

-----Input:-----
- First line will contain $N$, number of passengers. Then the $N$ lines follow. 
- $i$th line contains two integers $b_i, d_i$ , the boarding and departure mile of $i$th passenger.

-----Output:-----
Print a single value, the Infection Severity of the journey modulo $(10^9)+7$.

-----Constraints-----
- $0 \leq N \leq 100000$
- $-500000 \leq b_i \leq 500000$
- $-500000 \leq d_i \leq 500000$

-----Sample Input:-----
3

0 2

1 3

-1 4  

-----Sample Output:-----
12    

-----EXPLANATION:-----
Infection degree at :

-1 is 1

0 is 2

1 is 3

2 is 3

3 is 2

4 is 1

Calculation started at mile -1 and ended at mile 4. Infection Severity = 1+2+3+3+2+1 =12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Reca company makes monitors, the most popular of their models is AB999 with the screen size a × b centimeters. Because of some production peculiarities a screen parameters are integer numbers. Recently the screen sides ratio x: y became popular with users. That's why the company wants to reduce monitor AB999 size so that its screen sides ratio becomes x: y, at the same time they want its total area to be maximal of all possible variants. Your task is to find the screen parameters of the reduced size model, or find out that such a reduction can't be performed.

Input

The first line of the input contains 4 integers — a, b, x and y (1 ≤ a, b, x, y ≤ 2·109).

Output

If the answer exists, output 2 positive integers — screen parameters of the reduced size model. Output 0 0 otherwise.

Examples

Input

800 600 4 3


Output

800 600


Input

1920 1200 16 9


Output

1920 1080


Input

1 1 1 2


Output

0 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has many red balls and blue balls. Now, he will place them in a row.
Initially, there is no ball placed.
Takahashi, who is very patient, will do the following operation 10^{100} times:
 - Place A blue balls at the end of the row of balls already placed. Then, place B red balls at the end of the row.
How many blue balls will be there among the first N balls in the row of balls made this way?

-----Constraints-----
 - 1 \leq N \leq 10^{18}
 - A, B \geq 0
 - 0 < A + B \leq 10^{18}
 - All values in input are integers.

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

-----Output-----
Print the number of blue balls that will be there among the first N balls in the row of balls.

-----Sample Input-----
8 3 4

-----Sample Output-----
4

Let b denote a blue ball, and r denote a red ball. The first eight balls in the row will be bbbrrrrb, among which there are four blue balls.

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