vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
James Bond has a new plan for catching his enemy. There are some cities and directed roads between them, such that it is possible to travel between any two cities using these roads. When the enemy appears in some city, Bond knows her next destination but has no idea which path she will choose to move there. 

The city a is called interesting, if for each city b, there is exactly one simple path from a to b. By a simple path, we understand a sequence of distinct cities, such that for every two neighboring cities, there exists a directed road from the first to the second city. 

Bond's enemy is the mistress of escapes, so only the chase started in an interesting city gives the possibility of catching her. James wants to arrange his people in such cities. However, if there are not enough interesting cities, the whole action doesn't make sense since Bond's people may wait too long for the enemy.

You are responsible for finding all the interesting cities or saying that there is not enough of them. By not enough, James means strictly less than 20\% of all cities. 

Input

The first line contains one integer t (1 ≤ t ≤ 2 000) — the number of test cases. Each test case is described as follows:

The first line contains two integers n and m (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 2 ⋅ 10^5) — the number of cities and roads between them. Each of the following m lines contains two integers u, v (u ≠ v; 1 ≤ u, v ≤ n), which denote that there is a directed road from u to v.

You can assume that between each ordered pair of cities there is at most one road. The sum of n over all test cases doesn't exceed 10^5, and the sum of m doesn't exceed 2 ⋅ 10^5.

Output

If strictly less than 20\% of all cities are interesting, print -1. Otherwise, let k be the number of interesting cities. Print k distinct integers in increasing order — the indices of interesting cities.

Example

Input


4
3 3
1 2
2 3
3 1
3 6
1 2
2 1
2 3
3 2
1 3
3 1
7 10
1 2
2 3
3 1
1 4
4 5
5 1
4 6
6 7
7 4
6 1
6 8
1 2
2 3
3 4
4 5
5 6
6 1
6 2
5 1


Output


1 2 3 
-1
1 2 3 5 
-1

Note

In all drawings, if a city is colored green, then it is interesting; otherwise, it is colored red.

In the first sample, each city is interesting. 

<image>

In the second sample, no city is interesting. 

<image>

In the third sample, cities 1, 2, 3 and 5 are interesting. 

<image>

In the last sample, only the city 1 is interesting. It is strictly less than 20\% of all cities, so the answer is -1. 

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is one meeting room in a firm. There are N meetings in the form of (start[i], end[i]) where start[i] is start time of meeting i and end[i] is finish time of meeting i.
What is the maximum number of meetings that can be accommodated in the meeting room when only one meeting can be held in the meeting room at a particular time? 
Note: Start time of one chosen meeting can't be equal to the end time of the other chosen meeting.
Example 1:
Input:
N = 6
start[] = {1,3,0,5,8,5}
end[] =  {2,4,6,7,9,9}
Output: 
4
Explanation:
Maximum four meetings can be held with
given start and end timings.
The meetings are - (1, 2),(3, 4), (5,7) and (8,9)
Example 2:
Input:
N = 3
start[] = {10, 12, 20}
end[] = {20, 25, 30}
Output: 
1
Explanation:
Only one meetings can be held
with given start and end timings.
Your Task :
You don't need to read inputs or print anything. Complete the function maxMeetings() that takes two arrays start[] and end[] along with their size N as input parameters and returns the maximum number of meetings that can be held in the meeting room.
Expected Time Complexity : O(N*LogN)
Expected Auxilliary Space : O(N)
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ start[i] < end[i] ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"QAQ" is a word to denote an expression of crying. Imagine "Q" as eyes with tears and "A" as a mouth.

Now Diamond has given Bort a string consisting of only uppercase English letters of length n. There is a great number of "QAQ" in the string (Diamond is so cute!). $8$ illustration by 猫屋 https://twitter.com/nekoyaliu 

Bort wants to know how many subsequences "QAQ" are in the string Diamond has given. Note that the letters "QAQ" don't have to be consecutive, but the order of letters should be exact.


-----Input-----

The only line contains a string of length n (1 ≤ n ≤ 100). It's guaranteed that the string only contains uppercase English letters.


-----Output-----

Print a single integer — the number of subsequences "QAQ" in the string.


-----Examples-----
Input
QAQAQYSYIOIWIN

Output
4

Input
QAQQQZZYNOIWIN

Output
3



-----Note-----

In the first example there are 4 subsequences "QAQ": "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN".

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

square1001 and E869120 got lost in the grid world of $ H $ rows and $ W $ rows!

Said the god of this world.

"When you collect $ K $ apples and they meet, you'll be back in the original world."

Upon hearing this word, square1001 decided to collect more than $ K $ of apples and head to the square where E869120 is.




Here, each cell in the grid is represented as follows.

's': square1001 This is the square where you are.

'e': E869120 This is the square where you are.

'a': A square with one apple on it. You can get an apple the first time you visit this trout. There are no more than 20 squares on this grid.

'#': It's a wall. You cannot visit this square.

'.': A square with nothing. You can visit this square.




square1001 You try to achieve your goal by repeatedly moving from the square you are in to the squares that are adjacent to each other up, down, left, and right. However, you cannot get out of the grid.

square1001 Find the minimum number of moves you need to achieve your goal.

However, it is assumed that E869120 will not move. Also, square1001 shall be capable of carrying $ K $ or more of apples.

If the goal cannot be achieved, output "-1".

input

Input is given from standard input in the following format.

Let $ A_ {i, j} $ be the characters in the $ i $ square from the top of the grid and the $ j $ square from the left.


$ H $ $ W $ $ K $
$ A_ {1,1} A_ {1,2} A_ {1,3} \ cdots A_ {1, W} $
$ A_ {2,1} A_ {2,2} A_ {2,3} \ cdots A_ {2, W} $
$ A_ {3,1} A_ {3,2} A_ {3,3} \ cdots A_ {3, W} $
$ \ ldots $
$ A_ {H, 1} A_ {H, 2} A_ {H, 3} \ cdots A_ {H, W} $


output

square1001 Find the minimum number of moves you need to reach your goal. However, if this is not possible, output "-1".

However, insert a line break at the end.

Constraint

* $ 1 \ leq H \ leq 1000 $
* $ 1 \ leq W \ leq 1000 $
* $ 1 \ leq K \ leq 20 $
* $ H, W, K $ are integers.
* $ A_ {i, j} $ is one of's','e','a','#','.'.
* The grid contains only one's' and one'e'.
* The number of'a'in the grid is greater than or equal to $ K $ and less than or equal to $ 20 $.



Input example 1


5 5 2
s .. # a
. # ...
a # e. #
... # a
. # ...


Output example 1


14


Input example 2


7 7 3
.......
.s ... a.
a ## ... a
.. ### ..
.a # e # .a
. ### ..
a .. # .. a


Output example 2


-1


If the purpose cannot be achieved, output "-1".

Input example 3


12 12 10
. ##### ......
.## ..... # ...
.... a.a # a .. #
. # .. # a ......
..... a # s ..
..a ###. ##. #
.e #. #. #. # A ..
.. # a # ..... #.
.. ## a ......
.a ... a.a .. #.
a .... # a.aa ..
... a. # ... # a.


Output example 3


30






Example

Input

5 5 2
s..#a
.#...
a#e.#
...#a
.#...


Output

14

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
This year Alex has finished school, and now he is a first-year student of Berland State University. For him it was a total surprise that even though he studies programming, he still has to attend physical education lessons. The end of the term is very soon, but, unfortunately, Alex still hasn't attended a single lesson!

Since Alex doesn't want to get expelled, he wants to know the number of working days left until the end of the term, so he can attend physical education lessons during these days. But in BSU calculating the number of working days is a complicated matter:

There are *n* days left before the end of the term (numbered from 1 to *n*), and initially all of them are working days. Then the university staff sequentially publishes *q* orders, one after another. Each order is characterised by three numbers *l*, *r* and *k*:
 -  If *k*<==<=1, then all days from *l* to *r* (inclusive) become non-working days. If some of these days are made working days by some previous order, then these days still become non-working days; -  If *k*<==<=2, then all days from *l* to *r* (inclusive) become working days. If some of these days are made non-working days by some previous order, then these days still become working days. 
Help Alex to determine the number of working days left after each order!

Input Specification:
The first line contains one integer *n*, and the second line — one integer *q* (1<=≤<=*n*<=≤<=109, 1<=≤<=*q*<=≤<=3·105) — the number of days left before the end of the term, and the number of orders, respectively.

Then *q* lines follow, *i*-th line containing three integers *l**i*, *r**i* and *k**i* representing *i*-th order (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*, 1<=≤<=*k**i*<=≤<=2).

Output Specification:
Print *q* integers. *i*-th of them must be equal to the number of working days left until the end of the term after the first *i* orders are published.

Demo Input:
['4\n6\n1 2 1\n3 4 1\n2 3 2\n1 3 2\n2 4 1\n1 4 2\n']

Demo Output:
['2\n0\n2\n3\n1\n4\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The goal of this exercise is to convert a string to a new string where each character in the new string is `"("` if that character appears only once in the original string, or `")"` if that character appears more than once in the original string. Ignore capitalization when determining if a character is a duplicate.

## Examples
```
"din"      =>  "((("
"recede"   =>  "()()()"
"Success"  =>  ")())())"
"(( @"     =>  "))((" 
```

**Notes**

Assertion messages may be unclear about what they display in some languages. If you read `"...It Should encode XXX"`, the `"XXX"` is the expected result, not the input!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a connected undirected weighted graph consisting of $n$ vertices and $m$ edges.

You need to print the $k$-th smallest shortest path in this graph (paths from the vertex to itself are not counted, paths from $i$ to $j$ and from $j$ to $i$ are counted as one).

More formally, if $d$ is the matrix of shortest paths, where $d_{i, j}$ is the length of the shortest path between vertices $i$ and $j$ ($1 \le i < j \le n$), then you need to print the $k$-th element in the sorted array consisting of all $d_{i, j}$, where $1 \le i < j \le n$.


-----Input-----

The first line of the input contains three integers $n, m$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le \min\Big(\frac{n(n-1)}{2}, 2 \cdot 10^5\Big)$, $1 \le k \le \min\Big(\frac{n(n-1)}{2}, 400\Big)$ — the number of vertices in the graph, the number of edges in the graph and the value of $k$, correspondingly.

Then $m$ lines follow, each containing three integers $x$, $y$ and $w$ ($1 \le x, y \le n$, $1 \le w \le 10^9$, $x \ne y$) denoting an edge between vertices $x$ and $y$ of weight $w$.

It is guaranteed that the given graph is connected (there is a path between any pair of vertices), there are no self-loops (edges connecting the vertex with itself) and multiple edges (for each pair of vertices $x$ and $y$, there is at most one edge between this pair of vertices in the graph).


-----Output-----

Print one integer — the length of the $k$-th smallest shortest path in the given graph (paths from the vertex to itself are not counted, paths from $i$ to $j$ and from $j$ to $i$ are counted as one).


-----Examples-----
Input
6 10 5
2 5 1
5 3 9
6 2 2
1 3 1
5 1 8
6 5 10
1 6 5
6 4 6
3 6 2
3 4 5

Output
3

Input
7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 8
5 3 6
2 5 5
3 7 9
4 1 8
2 1 1

Output
9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Introduction and Warm-up (Highly recommended)

# [Playing With Lists/Arrays Series](https://www.codewars.com/collections/playing-with-lists-slash-arrays)
___

# Task

**_Given_** an *array/list [] of integers* , **_Find_**  *the Nth smallest element in this array of integers*
___

# Notes 

* **_Array/list_** size is *at least 3* .

* **_Array/list's numbers_** *could be a **_mixture_** of positives , negatives and zeros* .

* **_Repetition_** *in array/list's numbers could occur* , so **_don't Remove Duplications_** .
___

# Input >> Output Examples

```
nthSmallest({3,1,2} ,2) ==> return (2) 
```

## **_Explanation_**:

Since the passed number is **_2_** , Then * **_the second smallest_** element in this array/list is **_2_***  
___

```
nthSmallest({15,20,7,10,4,3} ,3) ==> return (7) 
```

## **_Explanation_**:

Since the passed number is **_3_** , Then * **_the third smallest_** element in this array/list is **_7_*** 
___
```
nthSmallest({2,169,13,-5,0,-1} ,4) ==> return (2) 
```

## **_Explanation_**:

Since the passed number is **_4_** , Then * **_the fourth smallest_** element in this array/list is **_2_*** 
___

```
nthSmallest({177,225,243,-169,-12,-5,2,92} ,5) ==> return (92) 
```
## **_Explanation_**:

Since the passed number is **_5_** , Then * **_the fifth smallest_** element in this array/list is **_92_*** 
___
___
___

# [Playing with Numbers Series](https://www.codewars.com/collections/playing-with-numbers)

# [Playing With Lists/Arrays Series](https://www.codewars.com/collections/playing-with-lists-slash-arrays)

# [For More Enjoyable Katas](http://www.codewars.com/users/MrZizoScream/authored)
___

## ALL translations are welcomed

## Enjoy Learning !!
# Zizou

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Me and my friends are ordering a big pizza to share. As you can imagine this is quite complicated, since everyone has different wishes about what should be on the pizza. For instance Gunnar wants bananas on the pizza, Emma doesn’t want bananas but wants olives, Marc wants there to be tomatoes, and so on. Fortunately, against all odds, we managed to come up with a selection of toppings such that everyone had at least $2/3$’s of their wishes fulfilled, which we unanimously decided was good enough.

But then, disaster struck! We sent out Lukáš to buy the pizza, but he accidentally lost the piece of paper on which we had written down our carefully selected list of toppings. Now we’re back at square one, and have to construct a new selection of toppings. Given how long it took us to find the original selection of toppings, we have decided to lower our standards a bit and just try to find a selection such that everyone has strictly more than $1/3$ of their wishes fulfilled.

Can you help us with this? If you do, you’ll get some pizza!

-----Input-----
The first line of input contains an integer $1 \le N \le 10000$, the number of friends in the group (including yourself). Each of the next $n$ lines contains the list of wishes of one of the friends. This list starts with an integer $1 \le w \le 30$, the number of wishes this friend has, followed by a space-separated list of wishes. Each wish is either “+<topping>” or “-<topping>” where <topping> is the name of a topping, indicating that this friend wants or does not want this topping. Each topping name appears at most once in each list.

Topping names are non-empty strings of up to $15$ lower-case English letters ‘a’-‘z’. There are at most $250$ different toppings.

-----Output-----
Output a list of toppings (without repetitions, separated by spaces or newlines) such that each friend has strictly more than $1/3$ of their wishes fulfilled. You may assume that there exists a list such that every friend has at least $2/3$ of their wishes fulfilled.

Your list of toppings is not allowed to contain any toppings that are not mentioned in the input, nor is it allowed to contain repetitions.

-----Examples-----
Sample Input:
1
4 +zucchini +mozzarella +mushrooms -artichoke
Sample Output:
zucchini
mozzarella
mushrooms
artichoke

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence $a_1, a_2, \dots, a_n$ consisting of $n$ integers.

You may perform the following operation on this sequence: choose any element and either increase or decrease it by one.

Calculate the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than $k$ times.


-----Input-----

The first line contains two integers $n$ and $k$ $(2 \le n \le 10^{5}, 1 \le k \le 10^{14})$ — the number of elements in the sequence and the maximum number of times you can perform the operation, respectively.

The second line contains a sequence of integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^{9})$.


-----Output-----

Print the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than $k$ times.


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

Output
2

Input
3 10
100 100 100

Output
0

Input
10 9
4 5 5 7 5 4 5 2 4 3

Output
1



-----Note-----

In the first example you can increase the first element twice and decrease the third element twice, so the sequence becomes $[3, 3, 5, 5]$, and the difference between maximum and minimum is $2$. You still can perform one operation after that, but it's useless since you can't make the answer less than $2$.

In the second example all elements are already equal, so you may get $0$ as the answer even without applying any operations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Count the number of divisors of a positive integer `n`.

Random tests go up to `n = 500000`.

## Examples
```python
divisors(4)  == 3  # 1, 2, 4
divisors(5)  == 2  # 1, 5
divisors(12) == 6  # 1, 2, 3, 4, 6, 12
divisors(30) == 8  # 1, 2, 3, 5, 6, 10, 15, 30
```

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasiliy is fond of solving different tasks. Today he found one he wasn't able to solve himself, so he asks you to help.

Vasiliy is given *n* strings consisting of lowercase English letters. He wants them to be sorted in lexicographical order (as in the dictionary), but he is not allowed to swap any of them. The only operation he is allowed to do is to reverse any of them (first character becomes last, second becomes one before last and so on).

To reverse the *i*-th string Vasiliy has to spent *c**i* units of energy. He is interested in the minimum amount of energy he has to spent in order to have strings sorted in lexicographical order.

String *A* is lexicographically smaller than string *B* if it is shorter than *B* (|*A*|<=&lt;<=|*B*|) and is its prefix, or if none of them is a prefix of the other and at the first position where they differ character in *A* is smaller than the character in *B*.

For the purpose of this problem, two equal strings nearby do not break the condition of sequence being sorted lexicographically.

Input Specification:
The first line of the input contains a single integer *n* (2<=≤<=*n*<=≤<=100<=000) — the number of strings.

The second line contains *n* integers *c**i* (0<=≤<=*c**i*<=≤<=109), the *i*-th of them is equal to the amount of energy Vasiliy has to spent in order to reverse the *i*-th string. 

Then follow *n* lines, each containing a string consisting of lowercase English letters. The total length of these strings doesn't exceed 100<=000.

Output Specification:
If it is impossible to reverse some of the strings such that they will be located in lexicographical order, print <=-<=1. Otherwise, print the minimum total amount of energy Vasiliy has to spent.

Demo Input:
['2\n1 2\nba\nac\n', '3\n1 3 1\naa\nba\nac\n', '2\n5 5\nbbb\naaa\n', '2\n3 3\naaa\naa\n']

Demo Output:
['1\n', '1\n', '-1\n', '-1\n']

Note:
In the second sample one has to reverse string 2 or string 3. To amount of energy required to reverse the string 3 is smaller.

In the third sample, both strings do not change after reverse and they go in the wrong order, so the answer is  - 1.

In the fourth sample, both strings consists of characters 'a' only, but in the sorted order string "aa" should go before string "aaa", thus the answer is  - 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have integer n. Calculate how many ways are there to fully cover belt-like area of 4n-2 triangles with diamond shapes. 

Diamond shape consists of two triangles. You can move, rotate or flip the shape, but you cannot scale it. 

2 coverings are different if some 2 triangles are covered by the same diamond shape in one of them and by different diamond shapes in the other one.

Please look at pictures below for better understanding.

<image> On the left you can see the diamond shape you will use, and on the right you can see the area you want to fill.

<image> These are the figures of the area you want to fill for n = 1, 2, 3, 4. 

You have to answer t independent test cases.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^{4}) — the number of test cases.

Each of the next t lines contains a single integer n (1 ≤ n ≤ 10^{9}).

Output

For each test case, print the number of ways to fully cover belt-like area of 4n-2 triangles using diamond shape. It can be shown that under given constraints this number of ways doesn't exceed 10^{18}.

Example

Input


2
2
1


Output


2
1

Note

In the first test case, there are the following 2 ways to fill the area:

<image>

In the second test case, there is a unique way to fill the area:

<image>

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