vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Vitaly and Cycle

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
After Vitaly was expelled from the university, he became interested in the graph theory.

Vitaly especially liked the cycles of an odd length in which each vertex occurs at most once.

Vitaly was wondering how to solve the following problem. You are given an undirected graph consisting of *n* vertices and *m* edges, not necessarily connected, without parallel edges and loops. You need to find *t* — the minimum number of edges that must be added to the given graph in order to form a simple cycle of an odd length, consisting of more than one vertex. Moreover, he must find *w* — the number of ways to add *t* edges in order to form a cycle of an odd length (consisting of more than one vertex). It is prohibited to add loops or parallel edges.

Two ways to add edges to the graph are considered equal if they have the same sets of added edges.

Since Vitaly does not study at the university, he asked you to help him with this task.

Input Specification:
The first line of the input contains two integers *n* and *m* ( — the number of vertices in the graph and the number of edges in the graph.

Next *m* lines contain the descriptions of the edges of the graph, one edge per line. Each edge is given by a pair of integers *a**i*, *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*) — the vertices that are connected by the *i*-th edge. All numbers in the lines are separated by a single space.

It is guaranteed that the given graph doesn't contain any loops and parallel edges. The graph isn't necessarily connected.

Output Specification:
Print in the first line of the output two space-separated integers *t* and *w* — the minimum number of edges that should be added to the graph to form a simple cycle of an odd length consisting of more than one vertex where each vertex occurs at most once, and the number of ways to do this.

Demo Input:
['4 4\n1 2\n1 3\n4 2\n4 3\n', '3 3\n1 2\n2 3\n3 1\n', '3 0\n']

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

Note:
The simple cycle is a cycle that doesn't contain any vertex twice.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Since you are in Britain, you definitely want to try British food. Unfortunately you will only have a single free evening, so you decided to try all the food you can get in one run. You plan a gigantic meal where you eat one British dish after the other. Clearly not every order of dishes is appropriate. For example, it is not acceptable to eat Blood Pudding directly after Cornish Hevva Cake, but it would be perfectly fine if you chose to eat Baked Beans in between.

You have compiled a comprehensive list of British dishes. For each dish you have also decided which other dishes are fit to be eaten directly afterwards. A menu is a sequence of dishes such that each dish (except the first) is fit to be eaten directly after the previous dish.

After some time studying the list of dishes, you noticed something odd: Whenever it is possible to find a menu in which a dish occurs twice (for example dishes $A$, then $B$, then $C$, then dish $A$ again), there can be at most four different types of dishes between the dish that occurred twice – excluding that dish itself. For example, it is impossible to find a menu like $A, B, C, D, E, F, A$, but it may be possible to find menus like $A, B, C, B, C, B, C, B, C, B, A$ or $A,B,C,D,E,A,B,C,D,E,A$.

But who wants to eat the same dish twice anyway? Clearly, you want to know how many dishes there can be in a menu without repeating any dish!

-----Input-----
The input consists of:
 - One line with two integers $n,m$ ($1 \leq n \leq 10^5$, $1\leq m \leq 10^6$), the number of dishes and compatibilities.
 - $m$ lines, each containing two integers $a$ and $b$ ($1 \leq a,b \leq n$), indicating that you can eat dish $b$ immediately after dish $a$.

Dishes are numbered from $1$ to $n$ in no particular order, and the compatibilities satisfy the constraint described above.

-----Output-----
A single integer indicating the maximum number of courses in a menu without repeated dishes.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be.



Suppose n lights are labeled as number [1, 2, 3 ..., n], function of these 4 buttons are given below:


Flip all the lights.
Flip lights with even numbers.
Flip lights with odd numbers.
Flip lights with (3k + 1) numbers, k = 0, 1, 2, ...




Example 1:

Input: n = 1, m = 1.
Output: 2
Explanation: Status can be: [on], [off]




Example 2:

Input: n = 2, m = 1.
Output: 3
Explanation: Status can be: [on, off], [off, on], [off, off]




Example 3:

Input: n = 3, m = 1.
Output: 4
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].



Note:
n and m both fit in range [0, 1000].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a lover of bacteria. You want to raise some bacteria in a box. 

Initially, the box is empty. Each morning, you can put any number of bacteria into the box. And each night, every bacterium in the box will split into two bacteria. You hope to see exactly x bacteria in the box at some moment. 

What is the minimum number of bacteria you need to put into the box across those days?


-----Input-----

The only line containing one integer x (1 ≤ x ≤ 10^9).


-----Output-----

The only line containing one integer: the answer.


-----Examples-----
Input
5

Output
2

Input
8

Output
1



-----Note-----

For the first sample, we can add one bacterium in the box in the first day morning and at the third morning there will be 4 bacteria in the box. Now we put one more resulting 5 in the box. We added 2 bacteria in the process so the answer is 2.

For the second sample, we can put one in the first morning and in the 4-th morning there will be 8 in the box. So the answer is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The annual student team competition in table tennis of students enrolled in University of Zagreb takes place next Saturday! Each team consists of $K$ students. The excited students, $N$ of them, are waiting in queue to register.

Krešo works at the registration desk. He doesn’t really feel like doing his job so he decided not to allow students to choose a team. He decided that the first team will consist of the first $K$ students standing in queue, the second team the following $K$ students, the third one the following $K$ students and so on…($N$ will be divisible by $K$ so nobody is left hanging.)

Ante has estimated the skill of each player with an integer. He would like to have the $K$ strongest players in the first team, the following $K$ strongest in the second team and so on…

Krešo has just taken a break and Ante decided to shift the students standing in queue so that he achieves his goal. The way he shifts them is that he tells a student to step out of the queue and go back in queue after another student or to go to the front of the queue. It takes him one minute to do this.

It’s possible that Krešo is going to return from his break any moment so Ante needs to achieve his goal as soon as possible. Help Ante determine the minimal number of minutes necessary for him to achieve his goal.

-----Input-----
The first line of input contains the integers $N$ and $K$ ($1 \leq K \leq N \leq 100000)$. The integer $N$ is going to divisible by $K$.

The second line contains $N$ space separated integers $v_ i$ ($1 \leq v_ i \leq 10^9$), the $i$-th number denotes the skill of the $i$-th player standing in queue – lower value means higher skill.

All contestants are going to have distinct levels of skill.

-----Output-----
The first and only line of output must contain the minimal required number of minutes.

-----Examples-----
Sample Input 1:
4 1
9 12 5 13
Sample Output 1:
1

Sample Input 2:
6 2
16 2 1 7 5 10
Sample Output 2:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A sequence a0, a1, ... is called a recurrent binary sequence, if each term ai (i = 0, 1, ...) is equal to 0 or 1 and there exist coefficients <image> such that 

an = c1·an - 1 + c2·an - 2 + ... + ck·an - k (mod 2),  for all n ≥ k. Assume that not all of ci are zeros.

Note that such a sequence can be uniquely recovered from any k-tuple {as, as + 1, ..., as + k - 1} and so it is periodic. Moreover, if a k-tuple contains only zeros, then the sequence contains only zeros, so this case is not very interesting. Otherwise the minimal period of the sequence is not greater than 2k - 1, as k-tuple determines next element, and there are 2k - 1 non-zero k-tuples. Let us call a sequence long if its minimal period is exactly 2k - 1. Your task is to find a long sequence for a given k, if there is any.

Input

Input contains a single integer k (2 ≤ k ≤ 50).

Output

If there is no long sequence for a given k, output "-1" (without quotes). Otherwise the first line of the output should contain k integer numbers: c1, c2, ..., ck (coefficients). The second line should contain first k elements of the sequence: a0, a1, ..., ak - 1. All of them (elements and coefficients) should be equal to 0 or 1, and at least one ci has to be equal to 1.

If there are several solutions, output any.

Examples

Input

2


Output

1 1
1 0


Input

3


Output

0 1 1
1 1 1

Note

1. In the first sample: c1 = 1, c2 = 1, so an = an - 1 + an - 2 (mod 2). Thus the sequence will be:

<image>

so its period equals 3 = 22 - 1.

2. In the second sample: c1 = 0, c2 = 1, c3 = 1, so an = an - 2 + an - 3 (mod 2). Thus our sequence is:

<image>

and its period equals 7 = 23 - 1.

Periods are colored.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Born a misinterpretation of [this kata](https://www.codewars.com/kata/simple-fun-number-334-two-beggars-and-gold/), your task here is pretty simple: given an array of values and an amount of beggars, you are supposed to return an array with the sum of what each beggar brings home, assuming they all take regular turns, from the first to the last.

For example: `[1,2,3,4,5]` for `2` beggars will return a result of `[9,6]`, as the first one takes `[1,3,5]`, the second collects `[2,4]`.

The same array with `3` beggars would have in turn have produced a better out come for the second beggar: `[5,7,3]`, as they will respectively take `[1,4]`, `[2,5]` and `[3]`.

Also note that not all beggars have to take the same amount of "offers", meaning that the length of the array is not necessarily a multiple of `n`; length can be even shorter, in which case the last beggars will of course take nothing (`0`).

***Note:*** in case you don't get why this kata is about *English* beggars, then you are not familiar on how religiously queues are taken in the kingdom ;)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Two samurai generals are discussing dinner plans after a battle, but they can't seem to agree.

The discussion gets heated and you are cannot risk favoring either of them as this might damage your political standing with either of the two clans the samurai generals belong to. Thus, the only thing left to do is find what the common ground of what they are saying is.

Compare the proposals with the following function: 
```python
def common_ground(s1,s2)
```

The parameters ```s1``` and ```s2``` are the strings representing what each of the generals said. You should output a string containing the words in ```s1``` that also occur in ```s2```.

Each word in the resulting string shall occur once, and the order of the words need to follow the order of the first occurence of each word in ```s2```.

If they are saying nothing in common, kill both samurai and blame a ninja. (output "death")

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob got a job as a system administrator in X corporation. His first task was to connect n servers with the help of m two-way direct connection so that it becomes possible to transmit data from one server to any other server via these connections. Each direct connection has to link two different servers, each pair of servers should have at most one direct connection. Y corporation, a business rival of X corporation, made Bob an offer that he couldn't refuse: Bob was asked to connect the servers in such a way, that when server with index v fails, the transmission of data between some other two servers becomes impossible, i.e. the system stops being connected. Help Bob connect the servers.

Input

The first input line contains 3 space-separated integer numbers n, m, v (3 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ v ≤ n), n — amount of servers, m — amount of direct connections, v — index of the server that fails and leads to the failure of the whole system.

Output

If it is impossible to connect the servers in the required way, output -1. Otherwise output m lines with 2 numbers each — description of all the direct connections in the system. Each direct connection is described by two numbers — indexes of two servers, linked by this direct connection. The servers are numbered from 1. If the answer is not unique, output any.

Examples

Input

5 6 3


Output

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


Input

6 100 1


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There was a girl who had a hobby of Othello. I enjoy Othello with my family when I have time.

One day, the girl tried to play Othello as usual. However, everyone was so busy that no one played. So I came up with a game that can be played by one person using Othello's board and spinning top.

problem

Othello pieces are arranged so that the top surface is black or white in all the squares of the vertical \\ (R \\) ​​square and the horizontal \\ (C \\) square.

Consider repeating the operation of "selecting a certain square and turning over all the pieces in the vertical, horizontal, and diagonal directions" as shown in the figure below. Find the number of operations that make the tops of all the pieces white. However, the following conditions must be met.

* You cannot operate the same square twice
* Do not distinguish the order of operations
* It is possible to continue the operation after the top surface of all the pieces has turned white.



<image>

input

The integer \\ (R \\) ​​and the integer \\ (C \\) are given on the first line, separated by blanks.

Subsequently, \\ (R \\) ​​lines are given \\ (C \\) integer values ​​(0 or 1), respectively. The \\ (c \\) th integer on the \\ (r \\) line represents the state of the square (r, c).

1 indicates that the upper surface is black, and 0 indicates that the upper surface is white.

output

If you can make the top surface of all the pieces on the board white, output the remainder of dividing the number of such operations by \\ (1000000009 (= 10 ^ 9 + 9) \\) on one line.

If you can't make the tops of all the pieces on the board white, print \\ (0 \\) on one line.

Constraint

* \\ (1 \ leq R \ leq 50, 1 \ leq C \ leq 50 \\)



Sample input / output

Input 1


13
1 1 1


Output 1


Four


\\ (\\ {(1,1) \\}, \\ {(1,2) \\}, \\ {(1,3) \\}, \\ {(1,1), (1) , 2), (1,3) \\} \\).

Input 2


13
1 0 1


Output 2


0


Input 3


twenty four
0 1 0 1
1 0 1 0


Output 3


1






Example

Input

1 3
1 1 1


Output

4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mancala is a game famous in the Middle East. It is played on a board that consists of 14 holes.  [Image] 

Initially, each hole has $a_i$ stones. When a player makes a move, he chooses a hole which contains a positive number of stones. He takes all the stones inside it and then redistributes these stones one by one in the next holes in a counter-clockwise direction.

Note that the counter-clockwise order means if the player takes the stones from hole $i$, he will put one stone in the $(i+1)$-th hole, then in the $(i+2)$-th, etc. If he puts a stone in the $14$-th hole, the next one will be put in the first hole.

After the move, the player collects all the stones from holes that contain even number of stones. The number of stones collected by player is the score, according to Resli.

Resli is a famous Mancala player. He wants to know the maximum score he can obtain after one move.


-----Input-----

The only line contains 14 integers $a_1, a_2, \ldots, a_{14}$ ($0 \leq a_i \leq 10^9$) — the number of stones in each hole.

It is guaranteed that for any $i$ ($1\leq i \leq 14$) $a_i$ is either zero or odd, and there is at least one stone in the board.


-----Output-----

Output one integer, the maximum possible score after one move.


-----Examples-----
Input
0 1 1 0 0 0 0 0 0 7 0 0 0 0

Output
4

Input
5 1 1 1 1 0 0 0 0 0 0 0 0 0

Output
8



-----Note-----

In the first test case the board after the move from the hole with $7$ stones will look like 1 2 2 0 0 0 0 0 0 0 1 1 1 1. Then the player collects the even numbers and ends up with a score equal to $4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Pavlopolis University where Noora studies it was decided to hold beauty contest "Miss Pavlopolis University". Let's describe the process of choosing the most beautiful girl in the university in more detail.

The contest is held in several stages. Suppose that exactly n girls participate in the competition initially. All the participants are divided into equal groups, x participants in each group. Furthermore the number x is chosen arbitrarily, i. e. on every stage number x can be different. Within each group the jury of the contest compares beauty of the girls in the format "each with each". In this way, if group consists of x girls, then <image> comparisons occur. Then, from each group, the most beautiful participant is selected. Selected girls enter the next stage of the competition. Thus if n girls were divided into groups, x participants in each group, then exactly <image> participants will enter the next stage. The contest continues until there is exactly one girl left who will be "Miss Pavlopolis University"

But for the jury this contest is a very tedious task. They would like to divide the girls into groups in each stage so that the total number of pairwise comparisons of the girls is as few as possible. Let f(n) be the minimal total number of comparisons that should be made to select the most beautiful participant, if we admit n girls to the first stage.

The organizers of the competition are insane. They give Noora three integers t, l and r and ask the poor girl to calculate the value of the following expression: t0·f(l) + t1·f(l + 1) + ... + tr - l·f(r). However, since the value of this expression can be quite large the organizers ask her to calculate it modulo 109 + 7. If Noora can calculate the value of this expression the organizers promise her to help during the beauty contest. But the poor girl is not strong in mathematics, so she turned for help to Leha and he turned to you.

Input

The first and single line contains three integers t, l and r (1 ≤ t < 109 + 7, 2 ≤ l ≤ r ≤ 5·106).

Output

In the first line print single integer — the value of the expression modulo 109 + 7.

Example

Input

2 2 4


Output

19

Note

Consider the sample.

It is necessary to find the value of <image>.

f(2) = 1. From two girls you can form only one group of two people, in which there will be one comparison.

f(3) = 3. From three girls you can form only one group of three people, in which there will be three comparisons.

f(4) = 3. From four girls you can form two groups of two girls each. Then at the first stage there will be two comparisons, one in each of the two groups. In the second stage there will be two girls and there will be one comparison between them. Total 2 + 1 = 3 comparisons. You can also leave all girls in same group in the first stage. Then <image> comparisons will occur. Obviously, it's better to split girls into groups in the first way.

Then the value of the expression is <image>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
'Jeopardy!' is an intellectual game where players answer questions and earn points. Company Q conducts a simplified 'Jeopardy!' tournament among the best IT companies. By a lucky coincidence, the old rivals made it to the finals: company R1 and company R2. 

The finals will have n questions, m of them are auction questions and n - m of them are regular questions. Each question has a price. The price of the i-th question is a_{i} points. During the game the players chose the questions. At that, if the question is an auction, then the player who chose it can change the price if the number of his current points is strictly larger than the price of the question. The new price of the question cannot be less than the original price and cannot be greater than the current number of points of the player who chose the question. The correct answer brings the player the points equal to the price of the question. The wrong answer to the question reduces the number of the player's points by the value of the question price.

The game will go as follows. First, the R2 company selects a question, then the questions are chosen by the one who answered the previous question correctly. If no one answered the question, then the person who chose last chooses again.

All R2 employees support their team. They want to calculate what maximum possible number of points the R2 team can get if luck is on their side during the whole game (they will always be the first to correctly answer questions). Perhaps you are not going to be surprised, but this problem was again entrusted for you to solve.


-----Input-----

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 100; m ≤ min(n, 30)) — the total number of questions and the number of auction questions, correspondingly. The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^7) — the prices of the questions. The third line contains m distinct integers b_{i} (1 ≤ b_{i} ≤ n) — the numbers of auction questions. Assume that the questions are numbered from 1 to n.


-----Output-----

In the single line, print the answer to the problem — the maximum points the R2 company can get if it plays optimally well. It is guaranteed that the answer fits into the integer 64-bit signed type.


-----Examples-----
Input
4 1
1 3 7 5
3

Output
18

Input
3 2
10 3 8
2 3

Output
40

Input
2 2
100 200
1 2

Output
400

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given N elements and your task is to Implement a Stack in which you can get a minimum element in O(1) time.
Example 1:
Input:
push(2)
push(3)
pop()
getMin()
push(1)
getMin()
Output: 2 1
Explanation: In the first test case for
query 
push(2)  Insert 2 into the stack.
         The stack will be {2}
push(3)  Insert 3 into the stack.
         The stack will be {2 3}
pop()    Remove top element from stack 
         Poped element will be 3 the
         stack will be {2}
getMin() Return the minimum element
         min element will be 2 
push(1)  Insert 1 into the stack.
         The stack will be {2 1}
getMin() Return the minimum element
         min element will be 1
Your Task:
You are required to complete the three methods push() which takes one argument an integer 'x' to be pushed into the stack, pop() which returns an integer popped out from the stack, and getMin() which returns the min element from the stack. (-1 will be returned if for pop() and getMin() the stack is empty.)
Expected Time Complexity: O(1) for all the 3 methods.
Expected Auxiliary Space: O(1) for all the 3 methods.
Constraints:
1 <= Number of queries <= 100
1 <= values of the stack <= 100

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