vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given a program you want to execute as a set of tasks organized in a dependency graph. The dependency graph is a directed acyclic graph: each task can depend on results of one or several other tasks, and there are no directed circular dependencies between tasks. A task can only be executed if all tasks it depends on have already completed.

Some of the tasks in the graph can only be executed on a coprocessor, and the rest can only be executed on the main processor. In one coprocessor call you can send it a set of tasks which can only be executed on it. For each task of the set, all tasks on which it depends must be either already completed or be included in the set. The main processor starts the program execution and gets the results of tasks executed on the coprocessor automatically.

Find the minimal number of coprocessor calls which are necessary to execute the given program.


-----Input-----

The first line contains two space-separated integers N (1 ≤ N ≤ 10^5) — the total number of tasks given, and M (0 ≤ M ≤ 10^5) — the total number of dependencies between tasks.

The next line contains N space-separated integers $E_{i} \in \{0,1 \}$. If E_{i} = 0, task i can only be executed on the main processor, otherwise it can only be executed on the coprocessor.

The next M lines describe the dependencies between tasks. Each line contains two space-separated integers T_1 and T_2 and means that task T_1 depends on task T_2 (T_1 ≠ T_2). Tasks are indexed from 0 to N - 1. All M pairs (T_1, T_2) are distinct. It is guaranteed that there are no circular dependencies between tasks.


-----Output-----

Output one line containing an integer — the minimal number of coprocessor calls necessary to execute the program.


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

Output
2

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

Output
1



-----Note-----

In the first test, tasks 1 and 3 can only be executed on the coprocessor. The dependency graph is linear, so the tasks must be executed in order 3 -> 2 -> 1 -> 0. You have to call coprocessor twice: first you call it for task 3, then you execute task 2 on the main processor, then you call it for for task 1, and finally you execute task 0 on the main processor.

In the second test, tasks 0, 1 and 2 can only be executed on the coprocessor. Tasks 1 and 2 have no dependencies, and task 0 depends on tasks 1 and 2, so all three tasks 0, 1 and 2 can be sent in one coprocessor call. After that task 3 is executed on the main processor.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Johanna knows mind reading magic, or so she says. Her new trick consists of lining up $N$ decks of cards, each deck having $K$ cards numbered from $1$ to $K$. She asks you to think of a number $T$ between $1$ and $N \cdot K$ and to focus your thoughts on it. Then, by scanning the energy profiles emitted from your brain activity, she carefully picks one card from each of the $N$ decks. Magically, the sum of the numbers on the $N$ picked cards is exactly the number that you were thinking of! After staring at her in disbelief for quite a while, you suspect it might be a trick she pulls on many people, and that she just picks the cards at random and happened to get it right with you just by chance.

You start wondering just how large that chance was. You could easily compute the number of ways to pick one card from each deck, but how many of these ways have the correct sum?

-----Input-----
The first line contains three space-separated integers $1 \le N \le 100$, $1 \le K \le 50$, $1 \le T \le N \cdot K$ – the number of decks, the number of cards in each deck, and the number you were thinking of, respectively.

-----Output-----
Output a single integer – the number of ways Johanna could have picked a card from each deck, such that the picked cards sum up to $T$. Since this number can be very large, output it modulo $1000000009$.

-----Examples-----
Sample Input 1:
5 2 6
Sample Output 1:
5

Sample Input 2:
5 5 25
Sample Output 2:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Zane the wizard is going to perform a magic show shuffling the cups.

There are n cups, numbered from 1 to n, placed along the x-axis on a table that has m holes on it. More precisely, cup i is on the table at the position x = i.

The problematic bone is initially at the position x = 1. Zane will confuse the audience by swapping the cups k times, the i-th time of which involves the cups at the positions x = u_{i} and x = v_{i}. If the bone happens to be at the position where there is a hole at any time, it will fall into the hole onto the ground and will not be affected by future swapping operations.

Do not forget that Zane is a wizard. When he swaps the cups, he does not move them ordinarily. Instead, he teleports the cups (along with the bone, if it is inside) to the intended positions. Therefore, for example, when he swaps the cup at x = 4 and the one at x = 6, they will not be at the position x = 5 at any moment during the operation. [Image] 

Zane’s puppy, Inzane, is in trouble. Zane is away on his vacation, and Inzane cannot find his beloved bone, as it would be too exhausting to try opening all the cups. Inzane knows that the Codeforces community has successfully helped Zane, so he wants to see if it could help him solve his problem too. Help Inzane determine the final position of the bone.


-----Input-----

The first line contains three integers n, m, and k (2 ≤ n ≤ 10^6, 1 ≤ m ≤ n, 1 ≤ k ≤ 3·10^5) — the number of cups, the number of holes on the table, and the number of swapping operations, respectively.

The second line contains m distinct integers h_1, h_2, ..., h_{m} (1 ≤ h_{i} ≤ n) — the positions along the x-axis where there is a hole on the table.

Each of the next k lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — the positions of the cups to be swapped.


-----Output-----

Print one integer — the final position along the x-axis of the bone.


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

Output
1
Input
5 1 2
2
1 2
2 4

Output
2


-----Note-----

In the first sample, after the operations, the bone becomes at x = 2, x = 5, x = 7, and x = 1, respectively.

In the second sample, after the first operation, the bone becomes at x = 2, and falls into the hole onto the ground.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
SKIT’s canteen sells Patties in packages of 6, 9 or 20 . Thus, it is possible, for example, to buy exactly 15 Patties (with one package of 6 and a second package of 9), but it is not possible to buy exactly 16 Patties, since no non- negative integer combination of 6's, 9's and 20's add up to 16. To determine if it is possible to buy exactly n Patties, one has to find non-negative integer values of a, b, and c such that

6a+9b+20c=n

Being an Engineer you are given task to find out whether an order is packable or not.

Input:

First line of the input contains an integer T, denoting the number of test cases, only to be followed by T lines each containing the order units U.

Output:

Output contains T lines, each having either True or False depending upon if the order is packable.

Constraints:

1 ≤ T ≤ 50
1 ≤ U ≤ 10^7

SAMPLE INPUT
2
45
1

SAMPLE OUTPUT
True
False

Explanation

As evident that no package is available for 1 unit but for 45 units ,it can be packaged in 5 : 9 unit packs or 
6 : 6 unit packs and 1 : 9 unit pack

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of strings words and a string chars.
A string is good if it can be formed by characters from chars (each character can only be used once).
Return the sum of lengths of all good strings in words.
 
Example 1:
Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: 
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:
Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: 
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

 
Note:

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
All strings contain lowercase English letters only.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
People in the Tomskaya region like magic formulas very much. You can see some of them below.

Imagine you are given a sequence of positive integer numbers p_1, p_2, ..., p_{n}. Lets write down some magic formulas:$q_{i} = p_{i} \oplus(i \operatorname{mod} 1) \oplus(i \operatorname{mod} 2) \oplus \cdots \oplus(i \operatorname{mod} n)$$Q = q_{1} \oplus q_{2} \oplus \ldots \oplus q_{n}$

Here, "mod" means the operation of taking the residue after dividing.

The expression $x \oplus y$ means applying the bitwise xor (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 by "^", in Pascal — by "xor".

People in the Tomskaya region like magic formulas very much, but they don't like to calculate them! Therefore you are given the sequence p, calculate the value of Q.


-----Input-----

The first line of the input contains the only integer n (1 ≤ n ≤ 10^6). The next line contains n integers: p_1, p_2, ..., p_{n} (0 ≤ p_{i} ≤ 2·10^9).


-----Output-----

The only line of output should contain a single integer — the value of Q.


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

Output
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
If you have not ever heard the term **Arithmetic Progrossion**, refer to: 
http://www.codewars.com/kata/find-the-missing-term-in-an-arithmetic-progression/python

And here is an unordered version. Try if you can survive lists of **MASSIVE** numbers (which means time limit should be considered). :D

Note: Don't be afraid that the minimum or the maximum element in the list is missing, e.g. [4, 6, 3, 5, 2] is missing 1 or 7, but this case is excluded from the kata.

Example:

```python
find([3, 9, 1, 11, 13, 5]) # => 7
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Multi-core Processor

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The research center Q has developed a new multi-core processor. The processor consists of *n* cores and has *k* cells of cache memory. Consider the work of this processor.

At each cycle each core of the processor gets one instruction: either do nothing, or the number of the memory cell (the core will write an information to the cell). After receiving the command, the core executes it immediately. Sometimes it happens that at one cycle, multiple cores try to write the information into a single cell. Unfortunately, the developers did not foresee the possibility of resolving conflicts between cores, so in this case there is a deadlock: all these cores and the corresponding memory cell are locked forever. Each of the locked cores ignores all further commands, and no core in the future will be able to record an information into the locked cell. If any of the cores tries to write an information into some locked cell, it is immediately locked.

The development team wants to explore the deadlock situation. Therefore, they need a program that will simulate the processor for a given set of instructions for each core within *m* cycles . You're lucky, this interesting work is entrusted to you. According to the instructions, during the *m* cycles define for each core the number of the cycle, during which it will become locked. It is believed that initially all cores and all memory cells are not locked.

Input Specification:
The first line contains three integers *n*, *m*, *k* (1<=≤<=*n*,<=*m*,<=*k*<=≤<=100). Then follow *n* lines describing instructions. The *i*-th line contains *m* integers: *x**i*1,<=*x**i*2,<=...,<=*x**im* (0<=≤<=*x**ij*<=≤<=*k*), where *x**ij* is the instruction that must be executed by the *i*-th core at the *j*-th cycle. If *x**ij* equals 0, then the corresponding instruction is «do nothing». But if *x**ij* is a number from 1 to *k*, then the corresponding instruction is «write information to the memory cell number *x**ij*».

We assume that the cores are numbered from 1 to *n*, the work cycles are numbered from 1 to *m* and the memory cells are numbered from 1 to *k*.

Output Specification:
Print *n* lines. In the *i*-th line print integer *t**i*. This number should be equal to 0 if the *i*-th core won't be locked, or it should be equal to the number of the cycle when this core will be locked.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Furik loves painting stars. A star is a shape that results if we take a regular pentagon and paint all diagonals in it. 

<image>

Recently he decided to teach Rubik to paint stars. After many years of training Rubik could paint stars easily. But now Furik decided to test Rubik and complicated the task. Rubik must paint n stars, observing the following rules:

  * all stars must be painted in a single move (i.e. it is forbidden to take the pen away from the paper); 
  * it is forbidden to paint the same segment of non-zero length more than once; 
  * the stars can intersect only in their vertexes; 
  * the length of a side of the regular pentagon, in which Rubik paints each star, must equal 10. 



Help Rubik to cope with this hard task.

Input

A single line contains an integer (1 ≤ n ≤ 100) — the number of stars to paint.

Output

On the first line print an integer m (1 ≤ m ≤ 5·n). On the next m lines print coordinates of m distinct points with accuracy of at least 9 and at most 100 digits after decimal point. All coordinates should not exceed 5000 in their absolute value. On each of the next n lines print 5 integers — the indexes of the points that form the given star in the clockwise or counterclockwise order. On the next line print 5·n + 1 integers — the numbers of points in the order, in which Rubik paints stars. That is, if number with index i is ai, and number with index i + 1 is ai + 1, then points with indexes ai and ai + 1 will have a segment painted between them. 

You can consider all m printed points indexed from 1 to m in the order, in which they occur in the output. Separate the numbers on the lines with whitespaces.

Note that the answer has an imprecise validation. Try to obtain as accurate a solution as possible. The validator performs all calculations considering that the absolute error of a participant's answer is not more than 10 - 8.

Examples

Input

1


Output

5
3.830127018922193 3.366025403784439
-3.601321235851749 10.057331467373021
0.466045194906253 19.192786043799030
10.411264148588986 18.147501411122495
12.490381056766580 8.366025403784439
1 2 3 4 5
1 3 5 2 4 1

Note

The initial position of points in the sample is:

<image>

The order in which Rubik can paint segments is:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the TV quiz Monstermind, a contestant chooses a topic and is then asked questions about it during a fixed period of time. The contestant earns one point for each correct answer. When the time runs out, the contestant must be silent.

Teresa has figured out such a niche topic that she knows all possible questions that may be asked about it, as well as all the answers. Since the competition is fierce, she has decided to sometimes answer a question before the host finishes reading it. The host picks each question uniformly at random from the pool of possible questions, and each question may be asked multiple times. When reading a question, the host reads at a pace of one word per second.

Teresa can interrupt the host mid-question—between words, or even before hearing the first word—but not mid-word—that would be extremely impolite. Answering also takes one second, and the host will start reading another question immediately after an answer—unless Teresa interrupts again.

She wrote a program to help her choose the best moment to answer, and now there is only one question left for you. How many points does she expect to score?

For example, in the first sample test case the answer is completely determined after hearing one word, so it is optimal to answer after hearing it, and Teresa answers 2 questions correctly in 4 seconds. In the second sample test case, if the first word is What, then it takes too much time to wait for the question to finish. Therefore Teresa says Now! 4 times and expects to get $1/3$ of the answers right.

-----Input-----
The first line contains two integers $t$ and $n$ ($1 \leq t \leq 100$, $1 \leq n \leq 100\ 000$), the duration of the quiz and the number of questions. Each of the following $n$ lines contains a question, which is a space-separated list of words terminated by a question mark; and an answer, which is a single word.

Each word is a sequence of non-space ASCII printable characters, between the ASCII values of ‘!’ and ‘$\sim $’. Only the last word of a question has a question mark (‘?’). You can assume that no question is a prefix of another and that punctuation marks are part of a word. Words spelled with different upper/lower case are assumed to be different.

It is guaranteed that the total number of word characters is at most $100\ 000$.

-----Output-----
Output the expected score of an optimal strategy. Answers within a relative or absolute error of $10^{-6}$ will be accepted.

-----Examples-----
Sample Input:
4 4
How much is 6 times 9? 42
How much is 9 times 6? 42
Is there intelligent life on Earth? Probably
What is the air speed velocity of an unladen swallow? African?
Sample Output:
2.0000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N persons, conveniently numbered 1 through N. They will take 3y3s Challenge for N-1 seconds.

During the challenge, each person must look at each of the N-1 other persons for 1 seconds, in some order.

If any two persons look at each other during the challenge, the challenge ends in failure.

Find the order in which each person looks at each of the N-1 other persons, to be successful in the challenge.

Constraints

* 2 \leq N \leq 100

Input

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


N


Output

If there exists no way to be successful in the challenge, print `-1`.

If there exists a way to be successful in the challenge, print any such way in the following format:


A_{1,1} A_{1,2} ... A_{1, N-1}
A_{2,1} A_{2,2} ... A_{2, N-1}
:
A_{N,1} A_{N,2} ... A_{N, N-1}


where A_{i, j} is the index of the person that the person numbered i looks at during the j-th second.

Judging

The output is considered correct only if all of the following conditions are satisfied:

* 1 \leq A_{i,j} \leq N
* For each i, A_{i,1}, A_{i,2}, ... , A_{i, N-1} are pairwise distinct.
* Let X = A_{i, j}, then A_{X, j} \neq i always holds.

Examples

Input

7


Output

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


Input

2


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bessie and the cows are playing with sequences and need your help. They start with a sequence, initially containing just the number 0, and perform n operations. Each operation is one of the following:  Add the integer x_{i} to the first a_{i} elements of the sequence.  Append an integer k_{i} to the end of the sequence. (And hence the size of the sequence increases by 1)  Remove the last element of the sequence. So, the size of the sequence decreases by one. Note, that this operation can only be done if there are at least two elements in the sequence. 

After each operation, the cows would like to know the average of all the numbers in the sequence. Help them!


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 2·10^5) — the number of operations. The next n lines describe the operations. Each line will start with an integer t_{i} (1 ≤ t_{i} ≤ 3), denoting the type of the operation (see above). If t_{i} = 1, it will be followed by two integers a_{i}, x_{i} (|x_{i}| ≤ 10^3; 1 ≤ a_{i}). If t_{i} = 2, it will be followed by a single integer k_{i} (|k_{i}| ≤ 10^3). If t_{i} = 3, it will not be followed by anything.

It is guaranteed that all operations are correct (don't touch nonexistent elements) and that there will always be at least one element in the sequence.


-----Output-----

Output n lines each containing the average of the numbers in the sequence after the corresponding operation.

The answer will be considered correct if its absolute or relative error doesn't exceed 10^{ - 6}.


-----Examples-----
Input
5
2 1
3
2 3
2 1
3

Output
0.500000
0.000000
1.500000
1.333333
1.500000

Input
6
2 1
1 2 20
2 2
1 2 -3
3
3

Output
0.500000
20.500000
14.333333
12.333333
17.500000
17.000000



-----Note-----

In the second sample, the sequence becomes $\{0 \} \rightarrow \{0,1 \} \rightarrow \{20,21 \} \rightarrow \{20,21,2 \} \rightarrow \{17,18,2 \} \rightarrow \{17,18 \} \rightarrow \{17 \}$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan wants to write a letter to his friend. The letter is a string s consisting of lowercase Latin letters.

Unfortunately, when Ivan started writing the letter, he realised that it is very long and writing the whole letter may take extremely long time. So he wants to write the compressed version of string s instead of the string itself.

The compressed version of string s is a sequence of strings c_1, s_1, c_2, s_2, ..., c_{k}, s_{k}, where c_{i} is the decimal representation of number a_{i} (without any leading zeroes) and s_{i} is some string consisting of lowercase Latin letters. If Ivan writes string s_1 exactly a_1 times, then string s_2 exactly a_2 times, and so on, the result will be string s.

The length of a compressed version is |c_1| + |s_1| + |c_2| + |s_2|... |c_{k}| + |s_{k}|. Among all compressed versions Ivan wants to choose a version such that its length is minimum possible. Help Ivan to determine minimum possible length.


-----Input-----

The only line of input contains one string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 8000).


-----Output-----

Output one integer number — the minimum possible length of a compressed version of s.


-----Examples-----
Input
aaaaaaaaaa

Output
3

Input
abcab

Output
6

Input
cczabababab

Output
7



-----Note-----

In the first example Ivan will choose this compressed version: c_1 is 10, s_1 is a.

In the second example Ivan will choose this compressed version: c_1 is 1, s_1 is abcab.

In the third example Ivan will choose this compressed version: c_1 is 2, s_1 is c, c_2 is 1, s_2 is z, c_3 is 4, s_3 is ab.

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