vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Read problems statements in Mandarin Chinese  and Russian. 

Time flies fast, Chef’s sons are getting older, stronger and higher. Chef has got two sons and they don’t go well with each other. Their relations are getting worse day by day. Concerned Chef has now decided to separate them. Chef is very rich and he has got N cities (N is even). His sons are all he has and he must divide the cities into his sons equally.  There are some roads running between the cities. Chef has to destruct all the roads between cities of first and second sons. The destruction of road costis a lot of money. So Chef wants to save as much as he can. So you have to help Chef in finding out minimal cost to split cities to his sons.

------ Input ------ 

First line contains two space separated integers N, M denoting the number of cities and the number of the roads respectively. 

Each i^{th} of the following M lines contains three integers a_{i}, b_{i} and c_{i} denoting the road between the city with the number a_{i} and the city with the number b_{i}. The cost for it's destruction is c_{i}.  

------ Output ------ 

In a single line, output N / 2 numbers – the numbers of cities that will belong to the first son after the partition.

------ Scoring ------ 

Your score will be sum of all c_{i} of all edges that would be destroyed by Chef. Your score for the problem will be sum of scores for each test files.
Your solution will be tested against only on 20% of the test files during the contest and will be rejudged against 100% after the end of competition.

------ Constraints ------ 

$1 ≤ N ≤ 10^{6}$
$1 ≤ M ≤ 10^{6}$
$0 ≤ a_{i}, b_{i} < N$
$1 ≤ c_{i} ≤ 10^{9}$

------ Subtasks ------ 

Subtask 1:

$1 ≤ N ≤ 100$
$1 ≤ M ≤ 1000$

Subtask 2:

$100 ≤ N ≤ 2*10^{4}$
$1000 ≤ M ≤ 2*10^{5}$

Subtask 3:

$2*10^{4} ≤ N ≤ 10^{5}$
$2*10^{5} ≤ M ≤ 4*10^{5}$

Subtask 4:

$10^{5} ≤ N ≤ 10^{6}$
$4*10^{5} ≤ M ≤ 10^{6}$

------ Example ------ 

Input:
4 4
0 1 1 
1 2 2
2 3 3
3 0 4

Output:
1 2

------ Test data generation ------ 

Four plans are used:

$Complete graph with random edge weights$
$Complete bipartite graph with random edge weights$
$Random tree$
$Fully random graph$

The first two sections subtasks are generated with the usage of all 4 of them, third section is generated with the usage only of the fourth plan, and fourth section is generated with the plans number 3 and 4.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A little girl loves problems on bitwise operations very much. Here's one of them.

You are given two integers *l* and *r*. Let's consider the values of  for all pairs of integers *a* and *b* (*l*<=≤<=*a*<=≤<=*b*<=≤<=*r*). Your task is to find the maximum value among all considered ones.

Expression  means applying bitwise excluding or operation to integers *x* and *y*. The given operation exists in all modern programming languages, for example, in languages *C*++ and *Java* it is represented as "^", in *Pascal* — as "xor".

Input Specification:
The single line contains space-separated integers *l* and *r* (1<=≤<=*l*<=≤<=*r*<=≤<=1018).

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output Specification:
In a single line print a single integer — the maximum value of  for all pairs of integers *a*, *b* (*l*<=≤<=*a*<=≤<=*b*<=≤<=*r*).

Demo Input:
['1 2\n', '8 16\n', '1 1\n']

Demo Output:
['3\n', '31\n', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vanja and Miksi have already finished everything for this year at their university, so they decided to spend their free time playing a game with a binary sequence $A_1, A_2, \dots, A_N$ (i.e. a sequence containing only integers $0$ and $1$).
At the beginning of the game, Vanja and Miksi write down the expression $* A_1 * A_2 * A_3 * \ldots * A_N$ (note below that each $*$ is a placeholder and does not denote multiplication).
The players take turns alternately, starting with Vanja. The game lasts $N$ turns. In each turn, the current player must replace the first (leftmost) remaining $*$ by the sign $+$ or $-$ (or, equivalently, by the operation of addition or subtraction).
After the last turn, the boys calculate the resulting value $V$ of the expression. If $|V| \ge K$, the winner is Vanja; otherwise, the winner is Miksi.
Please predict the winner of the game if both players play optimally. 

-----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 $K$.
- The second line contains $N$ space-separated integers $A_1, A_2, \dots, A_N$.

-----Output-----
For each test case, print a single line containing one integer — $1$ if Vanja (the first player) is the winner or $2$ if Miksi (the second player) is the winner.

-----Constraints-----
- $1 \le T \le 50$
- $1 \le N \le 3 \cdot 10^4$
- $0 \le K \le 3 \cdot 10^4$
- $0 \le A_i \le 1$ for each valid $i$

-----Example Input-----
2
2 1
1 0
3 5
0 1 0

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

-----Explanation-----
Example case 1: $K = 1$, so if Vanja replaces the first $*$ by $+$, the value of the final expression will be $V = 1$; then, $K \le |V|$, so the winner is Vanja.
Example case 2: $K = 5$, but the absolute value of the final expression cannot be greater than $1$. The winner is Miksi.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Teacher brought a fruit basket for three students. The basket contains only Apples, Mangoes and Oranges. Student A knows a value $a$, the total number of Apples and Mangoes in the Basket, B knows a value $b$, the total number of Mangoes and Oranges in the basket and Student C knows a value $c$, the total number of Oranges and Apples in the Basket. Since the teacher brought it he knows a value $d$ , the total number of fruits in the basket. You have to determine the exact number of Apples , Mangoes and Oranges in the basket separately.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, four integers $a,b,c,d$. 

-----Output:-----
For each testcase, output in a single line the number of Apples , Mangoes and Oranges in this order.

-----Constraints-----
- $1 \leq T \leq 100$
- $0 \leq a \leq 1000$
- $0 \leq b \leq 1000$
- $0 \leq c \leq 1000$
- $0 \leq d \leq 1000$ 
-The Solution always exisits

-----Sample Input:-----
2

7 9 8 12

3 8 7 9

-----Sample Output:-----
3 4 5

1 2 6

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In the official contest this problem has a different statement, for which jury's solution was working incorrectly, and for this reason it was excluded from the contest. This mistake have been fixed and the current given problem statement and model solution corresponds to what jury wanted it to be during the contest.

Vova and Lesha are friends. They often meet at Vova's place and compete against each other in a computer game named The Ancient Papyri: Swordsink. Vova always chooses a warrior as his fighter and Leshac chooses an archer. After that they should choose initial positions for their characters and start the fight. A warrior is good at melee combat, so Vova will try to make the distance between fighters as small as possible. An archer prefers to keep the enemy at a distance, so Lesha will try to make the initial distance as large as possible.

There are *n* (*n* is always even) possible starting positions for characters marked along the *Ox* axis. The positions are given by their distinct coordinates *x*1,<=*x*2,<=...,<=*x**n*, two characters cannot end up at the same position.

Vova and Lesha take turns banning available positions, Vova moves first. During each turn one of the guys bans exactly one of the remaining positions. Banned positions cannot be used by both Vova and Lesha. They continue to make moves until there are only two possible positions remaining (thus, the total number of moves will be *n*<=-<=2). After that Vova's character takes the position with the lesser coordinate and Lesha's character takes the position with the bigger coordinate and the guys start fighting.

Vova and Lesha are already tired by the game of choosing positions, as they need to play it before every fight, so they asked you (the developer of the The Ancient Papyri: Swordsink) to write a module that would automatically determine the distance at which the warrior and the archer will start fighting if both Vova and Lesha play optimally.

Input Specification:
The first line on the input contains a single integer *n* (2<=≤<=*n*<=≤<=200<=000, *n* is even) — the number of positions available initially. The second line contains *n* distinct integers *x*1,<=*x*2,<=...,<=*x**n* (0<=≤<=*x**i*<=≤<=109), giving the coordinates of the corresponding positions.

Output Specification:
Print the distance between the warrior and the archer at the beginning of the fight, provided that both Vova and Lesha play optimally.

Demo Input:
['6\n0 1 3 7 15 31\n', '2\n73 37\n']

Demo Output:
['7\n', '36\n']

Note:
In the first sample one of the optimum behavior of the players looks like that:
 1.  Vova bans the position at coordinate 15; 1.  Lesha bans the position at coordinate 3; 1.  Vova bans the position at coordinate 31; 1.  Lesha bans the position at coordinate 1. 
After these actions only positions 0 and 7 will remain, and the distance between them is equal to 7.

In the second sample there are only two possible positions, so there will be no bans.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Johnny is a boy who likes to open and close lockers. He loves it so much that one day, when school was out, he snuck in just to play with the lockers.

Each locker can either be open or closed. If a locker is closed when Johnny gets to it, he opens it, and vice versa.

The lockers are numbered sequentially, starting at 1.

Starting at the first locker, Johnny runs down the row, opening each locker.

Then he runs all the way back to the beginning and runs down the row again, this time skipping to every other locker. (2,4,6, etc)

Then he runs all the way back and runs through again, this time skipping two lockers for every locker he opens or closes. (3,6,9, etc)

He continues this until he has finished running past the last locker (i.e. when the number of lockers he skips is greater than the number of lockers he has).

------

The equation could be stated as follows: 

> Johnny runs down the row of lockers `n` times, starting at the first locker each run and skipping `i` lockers as he runs, where `n` is the number of lockers there are in total and `i` is the current run.
    
The goal of this kata is to determine which lockers are open at the end of Johnny's running. 

The program accepts an integer giving the total number of lockers, and should output an array filled with the locker numbers of those which are open at the end of his run.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dima came to the horse land. There are n horses living in the land. Each horse in the horse land has several enemies (enmity is a symmetric relationship). The horse land isn't very hostile, so the number of enemies of each horse is at most 3.

Right now the horse land is going through an election campaign. So the horses trusted Dima to split them into two parts. At that the horses want the following condition to hold: a horse shouldn't have more than one enemy in its party.

Help Dima split the horses into parties. Note that one of the parties can turn out to be empty.

Input

The first line contains two integers n, m <image> — the number of horses in the horse land and the number of enemy pairs.

Next m lines define the enemy pairs. The i-th line contains integers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi), which mean that horse ai is the enemy of horse bi.

Consider the horses indexed in some way from 1 to n. It is guaranteed that each horse has at most three enemies. No pair of enemies occurs more than once in the input.

Output

Print a line, consisting of n characters: the i-th character of the line must equal "0", if the horse number i needs to go to the first party, otherwise this character should equal "1".

If there isn't a way to divide the horses as required, print -1.

Examples

Input

3 3
1 2
3 2
3 1


Output

100


Input

2 1
2 1


Output

00


Input

10 6
1 2
1 3
1 4
2 3
2 4
3 4


Output

0110000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chefina has an array A consisting of N positive integers.

A permutation subsequence of length M is a subsequence that represents a permutation of length M.
 
Now, Chefina asks Chef to find the count of permutation subsequences in array A.
The count can be very large, so output it modulo 1000000007 (10^{9} + 7).

As a reminder:
A subsequence of an array is obtained by deleting some (possibly zero) elements from the array without changing the order of the remaining elements.
A permutation of length M is an array of length M in which every element from 1 to M occurs exactly once.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the length of array A.
- The next line contains N space-separated integers, the elements of the array A.

------ Output Format ------ 

For each test case, output on a new line, the count of permutation subsequences in array A, modulo 10^{9} + 7.

------ Constraints ------ 

$1 ≤ T ≤ 2\cdot 10^{5}$
$1 ≤ N ≤ 2\cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9} $
- Sum of $N$ over all test cases does not exceed $2\cdot 10^{5}$. 

----- Sample Input 1 ------ 
2
5
1 2 3 2 4
6
1 3 5 8 9 8

----- Sample Output 1 ------ 
7
1
----- explanation 1 ------ 
Test case $1$: Chef can get $7$ permutation subsequences:
$[1]$ , $[1, 2]$ , $[1, 2]$ , $[1, 2, 3]$ , $[1, 3, 2]$ , $[1, 2, 3, 4]$ , $[1, 3, 2, 4]$.

Test case $2$: Chef can get $1$ permutation subsequence:
$[1]$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Limak is a little grizzly bear. He will once attack Deerland but now he can only destroy trees in role-playing games. Limak starts with a tree with one vertex. The only vertex has index 1 and is a root of the tree.

Sometimes, a game chooses a subtree and allows Limak to attack it. When a subtree is attacked then each of its edges is destroyed with probability <image>, independently of other edges. Then, Limak gets the penalty — an integer equal to the height of the subtree after the attack. The height is defined as the maximum number of edges on the path between the root of the subtree and any vertex in the subtree.

You must handle queries of two types.

  * 1 v denotes a query of the first type. A new vertex appears and its parent is v. A new vertex has the next available index (so, new vertices will be numbered 2, 3, ...). 
  * 2 v denotes a query of the second type. For a moment let's assume that the game allows Limak to attack a subtree rooted in v. Then, what would be the expected value of the penalty Limak gets after the attack? 



In a query of the second type, Limak doesn't actually attack the subtree and thus the query doesn't affect next queries.

Input

The first line of the input contains one integer q (1 ≤ q ≤ 500 000) — the number of queries.

Then, q lines follow. The i-th of them contains two integers typei and vi (1 ≤ typei ≤ 2). If typei = 1 then vi denotes a parent of a new vertex, while if typei = 2 then you should print the answer for a subtree rooted in vi.

It's guaranteed that there will be at least 1 query of the second type, that is, the output won't be empty.

It's guaranteed that just before the i-th query a vertex vi already exists.

Output

For each query of the second type print one real number —the expected value of the penalty if Limak attacks the given subtree. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct if <image>.

Examples

Input

7
1 1
1 1
2 1
1 2
1 3
2 2
2 1


Output

0.7500000000
0.5000000000
1.1875000000


Input

8
2 1
1 1
1 2
1 3
1 4
2 1
1 4
2 1


Output

0.0000000000
0.9375000000
0.9687500000

Note

Below, you can see the drawing for the first sample. Red circles denote queries of the second type.

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an unweighted tree with N$N$ nodes (numbered 1$1$ through N$N$). Let's denote the distance between any two nodes p$p$ and q$q$ by d(p,q)$d(p, q)$.
You should answer Q$Q$ queries. In each query, you are given parameters a$a$, da$d_a$, b$b$, db$d_b$, and you should find a node x$x$ such that d(x,a)=da$d(x, a) = d_a$ and d(x,b)=db$d(x, b) = d_b$, or determine that there is no such node.

-----Input-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first line of each test case contains two space-separated integers N$N$ and Q$Q$.
- Each of the next N−1$N-1$ lines contains two space-separated integers u$u$ and v$v$ denoting that nodes u$u$ and v$v$ are connected by an edge.
- Each of the next Q$Q$ lines contains four space-separated integers a$a$, da$d_a$, b$b$ and db$d_b$ describing a query.

-----Output-----
For each query, print a single line containing one integer ― the number of a node satisfying the given requirements, or −1$-1$ if no such node exists.
If there are multiple solutions, you may output any one.

-----Constraints-----
- 1≤T≤1,000$1 \le T \le 1,000$
- 1≤N,Q≤106$1 \le N, Q \le 10^6$
- 1≤u,v≤N$1 \le u, v \le N$
- the graph on the input is a tree
- 1≤a,b≤N$1 \le a, b \le N$
- 1≤da,db<N$1 \le d_a, d_b < N$
- the sum of N$N$ over all test cases does not exceed 106$10^6$
- the sum of Q$Q$ over all test cases does not exceed 106$10^6$

-----Subtasks-----
Subtask #1 (50 points):
- 1≤N,Q≤1,000$1 \le N, Q \le 1,000$
- the sum of N$N$ over all test cases does not exceed 1,000$1,000$
- the sum of Q$Q$ over all test cases does not exceed 1,000$1,000$
Subtask #2 (50 points): original constraints

-----Example Input-----
1
5 3
1 2
2 3
3 4
3 5
2 1 4 1
2 2 4 2
1 1 2 1

-----Example Output-----
3
5
-1

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
When little Petya grew up and entered the university, he started to take part in АСМ contests. Later he realized that he doesn't like how the АСМ contests are organised: the team could only have three members (and he couldn't take all his friends to the competitions and distribute the tasks between the team members efficiently), so he decided to organize his own contests PFAST Inc. — Petr and Friends Are Solving Tasks Corporation. PFAST Inc. rules allow a team to have unlimited number of members.

To make this format of contests popular he organised his own tournament. To create the team he will prepare for the contest organised by the PFAST Inc. rules, he chose several volunteers (up to 16 people) and decided to compile a team from them. Petya understands perfectly that if a team has two people that don't get on well, then the team will perform poorly. Put together a team with as many players as possible given that all players should get on well with each other.

Input Specification:
The first line contains two integer numbers *n* (1<=≤<=*n*<=≤<=16) — the number of volunteers, and *m* () — the number of pairs that do not get on. Next *n* lines contain the volunteers' names (each name is a non-empty string consisting of no more than 10 uppercase and/or lowercase Latin letters). Next *m* lines contain two names — the names of the volunteers who do not get on. The names in pair are separated with a single space. Each pair of volunteers who do not get on occurs exactly once. The strings are case-sensitive. All *n* names are distinct.

Output Specification:
The first output line should contain the single number *k* — the number of people in the sought team. Next *k* lines should contain the names of the sought team's participants in the lexicographical order. If there are several variants to solve the problem, print any of them. Petya might not be a member of the sought team.

Demo Input:
['3 1\nPetya\nVasya\nMasha\nPetya Vasya\n', '3 0\nPasha\nLesha\nVanya\n']

Demo Output:
['2\nMasha\nPetya\n', '3\nLesha\nPasha\nVanya\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Asterix, Obelix and their temporary buddies Suffix and Prefix has finally found the Harmony temple. However, its doors were firmly locked and even Obelix had no luck opening them.

A little later they found a string *s*, carved on a rock below the temple's gates. Asterix supposed that that's the password that opens the temple and read the string aloud. However, nothing happened. Then Asterix supposed that a password is some substring *t* of the string *s*.

Prefix supposed that the substring *t* is the beginning of the string *s*; Suffix supposed that the substring *t* should be the end of the string *s*; and Obelix supposed that *t* should be located somewhere inside the string *s*, that is, *t* is neither its beginning, nor its end.

Asterix chose the substring *t* so as to please all his companions. Besides, from all acceptable variants Asterix chose the longest one (as Asterix loves long strings). When Asterix read the substring *t* aloud, the temple doors opened. 

You know the string *s*. Find the substring *t* or determine that such substring does not exist and all that's been written above is just a nice legend.

Input Specification:
You are given the string *s* whose length can vary from 1 to 106 (inclusive), consisting of small Latin letters.

Output Specification:
Print the string *t*. If a suitable *t* string does not exist, then print "Just a legend" without the quotes.

Demo Input:
['fixprefixsuffix\n', 'abcdabc\n']

Demo Output:
['fix', 'Just a legend']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given $a$ uppercase Latin letters 'A' and $b$ letters 'B'.

The period of the string is the smallest such positive integer $k$ that $s_i = s_{i~mod~k}$ ($0$-indexed) for each $i$. Note that this implies that $k$ won't always divide $a+b = |s|$.

For example, the period of string "ABAABAA" is $3$, the period of "AAAA" is $1$, and the period of "AABBB" is $5$.

Find the number of different periods over all possible strings with $a$ letters 'A' and $b$ letters 'B'.


-----Input-----

The first line contains two integers $a$ and $b$ ($1 \le a, b \le 10^9$) — the number of letters 'A' and 'B', respectively.


-----Output-----

Print the number of different periods over all possible strings with $a$ letters 'A' and $b$ letters 'B'.


-----Examples-----
Input
2 4

Output
4

Input
5 3

Output
5



-----Note-----

All the possible periods for the first example:   $3$ "BBABBA"  $4$ "BBAABB"  $5$ "BBBAAB"  $6$ "AABBBB" 

All the possible periods for the second example:   $3$ "BAABAABA"  $5$ "BAABABAA"  $6$ "BABAAABA"  $7$ "BAABAAAB"  $8$ "AAAAABBB" 

Note that these are not the only possible strings for the given periods.

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