vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Cutting

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are a lot of things which could be cut — trees, paper, "the rope". In this problem you are going to cut a sequence of integers.

There is a sequence of integers, which contains the equal number of even and odd numbers. Given a limited budget, you need to make maximum possible number of cuts such that each resulting segment will have the same number of odd and even integers.

Cuts separate a sequence to continuous (contiguous) segments. You may think about each cut as a break between two adjacent elements in a sequence. So after cutting each element belongs to exactly one segment. Say, $[4, 1, 2, 3, 4, 5, 4, 4, 5, 5]$ $\to$ two cuts $\to$ $[4, 1 | 2, 3, 4, 5 | 4, 4, 5, 5]$. On each segment the number of even elements should be equal to the number of odd elements.

The cost of the cut between $x$ and $y$ numbers is $|x - y|$ bitcoins. Find the maximum possible number of cuts that can be made while spending no more than $B$ bitcoins.

Input Specification:
First line of the input contains an integer $n$ ($2 \le n \le 100$) and an integer $B$ ($1 \le B \le 100$) — the number of elements in the sequence and the number of bitcoins you have.

Second line contains $n$ integers: $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 100$) — elements of the sequence, which contains the equal number of even and odd numbers

Output Specification:
Print the maximum possible number of cuts which can be made while spending no more than $B$ bitcoins.

Demo Input:
['6 4\n1 2 5 10 15 20\n', '4 10\n1 3 2 4\n', '6 100\n1 2 3 4 5 6\n']

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

Note:
In the first sample the optimal answer is to split sequence between $2$ and $5$. Price of this cut is equal to $3$ bitcoins.

In the second sample it is not possible to make even one cut even with unlimited number of bitcoins.

In the third sample the sequence should be cut between $2$ and $3$, and between $4$ and $5$. The total price of the cuts is $1 + 1 = 2$ bitcoins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You took a peek on Thanos wearing Infinity Gauntlet. In the Gauntlet there is a place for six Infinity Gems:  the Power Gem of purple color,  the Time Gem of green color,  the Space Gem of blue color,  the Soul Gem of orange color,  the Reality Gem of red color,  the Mind Gem of yellow color. 

Using colors of Gems you saw in the Gauntlet determine the names of absent Gems.


-----Input-----

In the first line of input there is one integer $n$ ($0 \le n \le 6$) — the number of Gems in Infinity Gauntlet.

In next $n$ lines there are colors of Gems you saw. Words used for colors are: purple, green, blue, orange, red, yellow. It is guaranteed that all the colors are distinct. All colors are given in lowercase English letters.


-----Output-----

In the first line output one integer $m$ ($0 \le m \le 6$) — the number of absent Gems.

Then in $m$ lines print the names of absent Gems, each on its own line. Words used for names are: Power, Time, Space, Soul, Reality, Mind. Names can be printed in any order. Keep the first letter uppercase, others lowercase.


-----Examples-----
Input
4
red
purple
yellow
orange

Output
2
Space
Time

Input
0

Output
6
Time
Mind
Soul
Power
Reality
Space



-----Note-----

In the first sample Thanos already has Reality, Power, Mind and Soul Gems, so he needs two more: Time and Space.

In the second sample Thanos doesn't have any Gems, so he needs all six.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Friends are going to play console. They have two joysticks and only one charger for them. Initially first joystick is charged at a_1 percent and second one is charged at a_2 percent. You can connect charger to a joystick only at the beginning of each minute. In one minute joystick either discharges by 2 percent (if not connected to a charger) or charges by 1 percent (if connected to a charger).

Game continues while both joysticks have a positive charge. Hence, if at the beginning of minute some joystick is charged by 1 percent, it has to be connected to a charger, otherwise the game stops. If some joystick completely discharges (its charge turns to 0), the game also stops.

Determine the maximum number of minutes that game can last. It is prohibited to pause the game, i. e. at each moment both joysticks should be enabled. It is allowed for joystick to be charged by more than 100 percent.


-----Input-----

The first line of the input contains two positive integers a_1 and a_2 (1 ≤ a_1, a_2 ≤ 100), the initial charge level of first and second joystick respectively.


-----Output-----

Output the only integer, the maximum number of minutes that the game can last. Game continues until some joystick is discharged.


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

Output
6

Input
4 4

Output
5



-----Note-----

In the first sample game lasts for 6 minute by using the following algorithm:  at the beginning of the first minute connect first joystick to the charger, by the end of this minute first joystick is at 4%, second is at 3%;  continue the game without changing charger, by the end of the second minute the first joystick is at 5%, second is at 1%;  at the beginning of the third minute connect second joystick to the charger, after this minute the first joystick is at 3%, the second one is at 2%;  continue the game without changing charger, by the end of the fourth minute first joystick is at 1%, second one is at 3%;  at the beginning of the fifth minute connect first joystick to the charger, after this minute the first joystick is at 2%, the second one is at 1%;  at the beginning of the sixth minute connect second joystick to the charger, after this minute the first joystick is at 0%, the second one is at 2%. 

After that the first joystick is completely discharged and the game is stopped.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko is a huge fan of chess and programming, but typical chess soon became boring for him, so he started having fun with rook pieces.

He found a chessboard with $N$ rows and $N$ columns and placed $K$ rooks on it. Mirko’s game is made of the following rules:
 - Each rook’s power is determined by an integer.
 - A rook sees all the fields that are in his row or column except its own field.
 - We say that a field is attacked if the binary XOR of all the powers of the rooks that see the field is greater than $0$.

Notice that the field a rook is at can be attacked or not.

Initially, Mirko placed the rooks in a certain layout on the board and will make $P$ moves. After each move, determine how many fields are attacked. Every rook can be moved to any free field on the whole board (not only across column and row).

-----Input-----
The first line of input contains integers $N$, $K$, $P$ ($1 \leq N \leq 1\ 000\ 000\ 000$, $1 \leq K \leq 100\ 000$, $1 \leq P \leq 100\ 000$). Each of the following $K$ lines contains three integers $R$, $C$, $X$ ($1 \leq R, C \leq N$, $1 \leq X \leq 1\ 000\ 000\ 000$) which denote that initially there is a rook of power $X$ on the field $(R, C)$. Each of the following $P$ lines contains four integers $R_1$, $C_1$, $R_2$, $C_2$ ($1 \leq R_1, C_1, R_2, C_2 \leq N$) which denote that the rook has moved from field $(R_1, C_1 )$ to field $(R_2, C_2 )$. It is guaranteed that there will not be two rooks on one field at any point.

-----Output-----
The output must consist of $P$ lines, the $k$-th line containing the total number of attacked fields after $k$ moves.

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

Sample Input 2:
2 2 2
1 1 1
2 2 2
2 2 2 1
1 1 1 2
Sample Output 2:
4
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Detective Rust is investigating a homicide and he wants to chase down the murderer. The murderer knows he would definitely get caught if he takes the main roads for fleeing, so he uses the village roads (or side lanes) for running away from the crime scene.

Rust knows that the murderer will take village roads and he wants to chase him down. He is observing the city map, but it doesn't show the village roads (or side lanes) on it and shows only the main roads. 

The map of the city is a graph consisting $N$ nodes (labeled $\mbox{I}$ to $N$) where a specific given node $\mbox{S}$ represents the current position of Rust and the rest of the nodes denote other places in the city, and an edge between two nodes is a main road between two places in the city. It can be suitably assumed that an edge that doesn't exist/isn't shown on the map is a village road (side lane). That means, there is a village road between two nodes $\boldsymbol{\alpha}$ and $\boldsymbol{b}$ iff(if and only if) there is no city road between them.  

In this problem, distance is calculated as number of village roads (side lanes) between any two places in the city.

Rust wants to calculate the shortest distance from his position (Node $\mbox{S}$) to all the other places in the city if he travels only using the village roads (side lanes).

Note: The graph/map of the city is ensured to be a sparse graph.

Input Format

The first line contains $\mathbf{T}$, denoting the number of test cases. $\mathbf{T}$ testcases follow. 

First line of each test case has two integers $N$, denoting the number of cities in the map and $\mbox{M}$, denoting the number of roads in the map. 

The next $\mbox{M}$ lines each consist of two space-separated integers $\boldsymbol{x}$ and $y$ denoting a main road between city $\boldsymbol{x}$ and city $y$. 
The last line has an integer $\mbox{S}$, denoting the current position of Rust. 

Constraints

$1\leq T\leq10$  
$2\leq N\leq2\times10^5$  
$0\leq M\leq120000$  
$1\leq x,y,S\leq N$  

Note  

No nodes will have a road to itself.   
There will not be multiple edges between any pair of nodes i.e. there is at most one undirected edge between them.   
Graph is guaranteed to be sparse. 
It is guranteed that there will be a path between any pair of nodes using the side lanes.

Output Format

For each of T test cases, print a single line consisting of N-1 space separated integers, denoting the shortest distances of the remaining N-1 places from Rust's position (that is all distances, except the source node to itself) using the village roads/side lanes in ascending order based on vertex number.  

Sample Input 0
2
4 3
1 2
2 3
1 4
1
4 2
1 2
2 3
2

Sample Output 0
3 1 2
2 2 1

Explanation 0

The graph in the first testcase can be shown as:

Here the source node is 1 (marked S). 

The distance from 1 to 2 is 3. Path: 1 -> 3 -> 4 -> 2 

The distance from 1 to 3 is 1. Path: 1 -> 3 

The distance from 1 to 4 is 2. Path: 1 -> 3 -> 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer sequence a of length N. How many permutations p of the integers 1 through N satisfy the following condition?

* For each 1 ≤ i ≤ N, at least one of the following holds: p_i = a_i and p_{p_i} = a_i.



Find the count modulo 10^9 + 7.

Constraints

* 1 ≤ N ≤ 10^5
* a_i is an integer.
* 1 ≤ a_i ≤ N

Input

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


N
a_1 a_2 ... a_N


Output

Print the number of the permutations p that satisfy the condition, modulo 10^9 + 7.

Examples

Input

3
1 2 3


Output

4


Input

2
1 1


Output

1


Input

3
2 1 1


Output

2


Input

3
1 1 1


Output

0


Input

13
2 1 4 3 6 7 5 9 10 8 8 9 11


Output

6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Theta has been learning about powers of $2$ in school. She notices that some numbers when written out contain powers of $2$ in their digit representation: for instance, $12560$ contains $256$ which is a power of $2$. She has been wondering how many such numbers there are.

Can you write a program that counts how many numbers contain a given power of $2$?

-----Input-----
The input consists of a single line with two integers $n$ and $e$ ($0 \le n \le 15000000, 0 \le e \le 25$).

-----Output-----
Output a single integer that is equal to the number of distinct integers $k$ ($0 \le k \le n$) whose decimal representation contains the digits of $2^e$ as a substring.

-----Examples-----
Sample Input 1:
1000000 1
Sample Output 1:
468559

Sample Input 2:
1000000 5
Sample Output 2:
49401

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fatima commutes from KTH to home by subway every day. Today Robert decided to surprise Fatima by baking cookies and bringing them to an intermediate station. Fatima does not always take the same route home, because she loves to admire the artwork inside different stations in Stockholm. However, she always optimizes her travel by taking the shortest route. Can you tell Robert which station he should go to in order to surely intercept Fatima?

-----Input-----
The first line contains two integers $N$ and $M$, $1 \leq N,M \leq 100000$, where $N$ is the number of subway stations and $M$ is the number of subway links. $M$ lines follow, each with three integers $u$, $v$, $w$, $0 \leq u,v < N$, $0 < w \leq 1000000000$, meaning that there is a one-way link from $u$ to $v$ that takes $w$ seconds to complete. Note that different subway lines may serve the same route.

The last line contains two integers $s$ and $t$, $0 \leq s,t < N$ the number of the station closest to KTH and closest to home, respectively. It is possible to reach $t$ from $s$.

-----Output-----
A space separated list of all the station numbers $u$ such that all shortest paths from $s$ to $t$ pass through $u$, in increasing order.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Professional sport is more than hard work. It also is the equipment, designed by top engineers. As an example, let's take tennis. Not only should you be in great shape, you also need an excellent racket! In this problem your task is to contribute to the development of tennis and to help to design a revolutionary new concept of a racket!

The concept is a triangular racket. Ant it should be not just any triangle, but a regular one. As soon as you've chosen the shape, you need to stretch the net. By the time you came the rocket had n holes drilled on each of its sides. The holes divide each side into equal n + 1 parts. At that, the m closest to each apex holes on each side are made for better ventilation only and you cannot stretch the net through them. The next revolutionary idea as to stretch the net as obtuse triangles through the holes, so that for each triangle all apexes lay on different sides. Moreover, you need the net to be stretched along every possible obtuse triangle. That's where we need your help — help us to count the number of triangles the net is going to consist of.

Two triangles are considered to be different if their pictures on the fixed at some position racket are different.

Input

The first and the only input line contains two integers n, m <image>.

Output

Print a single number — the answer to the problem.

Examples

Input

3 0


Output

9


Input

4 0


Output

24


Input

10 1


Output

210


Input

8 4


Output

0

Note

For the following picture n = 8, m = 2. White circles are the holes for ventilation, red circles — holes for net stretching. One of the possible obtuse triangles is painted red. 

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After several latest reforms many tourists are planning to visit Berland, and Berland people understood that it's an opportunity to earn money and changed their jobs to attract tourists. Petya, for example, left the IT corporation he had been working for and started to sell souvenirs at the market.

This morning, as usual, Petya will come to the market. Petya has n different souvenirs to sell; ith souvenir is characterised by its weight w_{i} and cost c_{i}. Petya knows that he might not be able to carry all the souvenirs to the market. So Petya wants to choose a subset of souvenirs such that its total weight is not greater than m, and total cost is maximum possible.

Help Petya to determine maximum possible total cost.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 300000) — the number of Petya's souvenirs and total weight that he can carry to the market.

Then n lines follow. ith line contains two integers w_{i} and c_{i} (1 ≤ w_{i} ≤ 3, 1 ≤ c_{i} ≤ 10^9) — the weight and the cost of ith souvenir.


-----Output-----

Print one number — maximum possible total cost of souvenirs that Petya can carry to the market.


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

Output
0

Input
2 2
1 3
2 2

Output
3

Input
4 3
3 10
2 7
2 8
1 1

Output
10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A bipartite graph G = (V, E) is a graph in which the vertex set V can be divided into two disjoint subsets X and Y such that every edge e ∈ E has one end point in X and the other end point in Y.

A matching M is a subset of edges such that each node in V appears in at most one edge in M.

Given a bipartite graph, find the size of the matching which has the largest size.

Constraints

* 1 ≤ |X|, |Y| ≤ 100
* 0 ≤ |E| ≤ 10,000

Input


|X| |Y| |E|
x0 y0
x1 y1
:
x|E|-1 y|E|-1


|X| and |Y| are the number of vertices in X and Y respectively, and |E| is the number of edges in the graph G. The vertices in X are named with the numbers 0, 1,..., |X|-1, and vertices in Y are named with the numbers 0, 1,..., |Y|-1, respectively.

xi and yi are the node numbers from X and Y respectevely which represent the end-points of the i-th edge.

Output

Print the largest size of the matching.

Example

Input

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


Output

3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
This is an interactive problem.

Natasha is going to fly to Mars. Finally, Natasha sat in the rocket. She flies, flies... but gets bored. She wishes to arrive to Mars already! So she decides to find something to occupy herself. She couldn't think of anything better to do than to calculate the distance to the red planet.

Let's define $x$ as the distance to Mars. Unfortunately, Natasha does not know $x$. But it is known that $1 \le x \le m$, where Natasha knows the number $m$. Besides, $x$ and $m$ are positive integers.

Natasha can ask the rocket questions. Every question is an integer $y$ ($1 \le y \le m$). The correct answer to the question is $-1$, if $x&lt;y$, $0$, if $x=y$, and $1$, if $x&gt;y$. But the rocket is broken — it does not always answer correctly. Precisely: let the correct answer to the current question be equal to $t$, then, if the rocket answers this question correctly, then it will answer $t$, otherwise it will answer $-t$.

In addition, the rocket has a sequence $p$ of length $n$. Each element of the sequence is either $0$ or $1$. The rocket processes this sequence in the cyclic order, that is $1$-st element, $2$-nd, $3$-rd, $\ldots$, $(n-1)$-th, $n$-th, $1$-st, $2$-nd, $3$-rd, $\ldots$, $(n-1)$-th, $n$-th, $\ldots$. If the current element is $1$, the rocket answers correctly, if $0$ — lies. Natasha doesn't know the sequence $p$, but she knows its length — $n$.

You can ask the rocket no more than $60$ questions.

Help Natasha find the distance to Mars. Assume, that the distance to Mars does not change while Natasha is asking questions.

Your solution will not be accepted, if it does not receive an answer $0$ from the rocket (even if the distance to Mars is uniquely determined by the already received rocket's answers).

Input Specification:
The first line contains two integers $m$ and $n$ ($1 \le m \le 10^9$, $1 \le n \le 30$) — the maximum distance to Mars and the number of elements in the sequence $p$.

Output Specification:
none

Demo Input:
['5 2\n1\n-1\n-1\n1\n0\n']

Demo Output:
['1\n2\n4\n5\n3\n']

Note:
In the example, hacking would look like this:

5 2 3

1 0

This means that the current distance to Mars is equal to $3$, Natasha knows that it does not exceed $5$, and the rocket answers in order: correctly, incorrectly, correctly, incorrectly ...

Really:

on the first query ($1$) the correct answer is $1$, the rocket answered correctly: $1$;

on the second query ($2$) the correct answer is $1$, the rocket answered incorrectly: $-1$;

on the third query ($4$) the correct answer is $-1$, the rocket answered correctly: $-1$;

on the fourth query ($5$) the correct answer is $-1$, the rocket answered incorrectly: $1$;

on the fifth query ($3$) the correct and incorrect answer is $0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Misha and XOR

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
After Misha's birthday he had many large numbers left, scattered across the room. Now it's time to clean up and Misha needs to put them in a basket. He ordered this task to his pet robot that agreed to complete the task at certain conditions. Before the robot puts a number *x* to the basket, Misha should answer the question: is it possible to choose one or multiple numbers that already are in the basket, such that their XOR sum equals *x*? 

If the answer is positive, you also need to give the indexes of these numbers. If there are multiple options of choosing numbers, you are allowed to choose any correct option. After Misha's answer the robot puts the number to the basket.

Initially the basket is empty. Each integer you put in the basket takes some number. The first integer you put into the basket take number 0, the second integer takes number 1 and so on.

Misha needs to clean up the place as soon as possible but unfortunately, he isn't that good at mathematics. He asks you to help him.

Input Specification:
The first line contains number *m* (1<=≤<=*m*<=≤<=2000), showing how many numbers are scattered around the room.

The next *m* lines contain the numbers in the order in which the robot puts them in the basket. Each number is a positive integer strictly less than 10600 that doesn't contain leading zeroes.

Output Specification:
For each number either print a 0 on the corresponding line, if the number cannot be represented as a XOR sum of numbers that are in the basket, or print integer *k* showing how many numbers are in the representation and the indexes of these numbers. Separate the numbers by spaces. Each number can occur in the representation at most once.

Demo Input:
['7\n7\n6\n5\n4\n3\n2\n1\n', '2\n5\n5\n']

Demo Output:
['0\n0\n0\n3 0 1 2\n2 1 2\n2 0 2\n2 0 1\n', '0\n1 0\n']

Note:
The XOR sum of numbers is the result of bitwise sum of numbers modulo 2.

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