vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. 

You are given a sequence A in which every element is a pair of integers  i.e  A = [(a_{1}, w_{1}), (a_{2}, w_{2}),..., (a_{N}, w_{N})].

For a subseqence B = [(b_{1}, v_{1}), (b_{2}, v_{2}), ...., (b_{M}, v_{M})] of the given sequence : 

We call it increasing if for every i (1 <= i < M ) , b_{i} < b_{i+1}.
Weight(B) = v_{1} + v_{2} + ... + v_{M}.  

Task: 

Given a sequence, output the maximum weight formed by an increasing subsequence.

Input: 

The first line of input contains a single integer T. T test-cases follow. The first line of each test-case contains an integer N. The next line contains a_{1}, a_{2} ,... , a_{N} separated by a single space. The next line contains w_{1}, w_{2}, ..., w_{N} separated by a single space.

Output: 

For each test-case output a single integer: The maximum weight of increasing subsequences of the given sequence.  

Constraints: 

1 <= T <= 5 

1 <= N <= 150000 

1 <= a_{i} <= $10^{9}$, where i ∈ [1..N] 

1 <= w_{i} <= $10^{9}$, where i ∈ [1..N]  

Sample Input:

2  
4  
1 2 3 4  
10 20 30 40  
8  
1 2 3 4 1 2 3 4  
10 20 30 40 15 15 15 50

Sample Output:

100  
110

Explanation: 

In the first sequence, the maximum size increasing subsequence is 4, and there's only one of them. We choose B = [(1, 10), (2, 20), (3, 30), (4, 40)], and we have Weight(B) = 100.

In the second sequence, the maximum size increasing subsequence is still 4, but there are now 5 possible subsequences:

1 2 3 4  
10 20 30 40

1 2 3 4  
10 20 30 50

1 2 3 4  
10 20 15 50

1 2 3 4  
10 15 15 50

1 2 3 4  
15 15 15 50

Of those, the one with the greatest weight is B = [(1, 10), (2, 20), (3, 30), (4, 50)], with Weight(B) = 110.

Please note that this is not the maximum weight generated from picking the highest value element of each index. That value, 115, comes from [(1, 15), (2, 20), (3, 30), (4, 50)], which is not a valid subsequence because it cannot be created by only deleting elements in the original sequence.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let us denote by d(n) the sum of all divisors of the number n, i.e. d(n) = ∑_{k | n} k.

For example, d(1) = 1, d(4) = 1+2+4=7, d(6) = 1+2+3+6=12.

For a given number c, find the minimum n such that d(n) = c.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

Each test case is characterized by one integer c (1 ≤ c ≤ 10^7).

Output

For each test case, output: 

  * "-1" if there is no such n that d(n) = c; 
  * n, otherwise. 

Example

Input


12
1
2
3
4
5
6
7
8
9
10
39
691


Output


1
-1
2
3
-1
5
4
7
-1
-1
18
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fizza is a cute girl and she wants to be more beautiful.
So she approached a magician to increase her beauty magically. But the magician's 
glasses accidently got locked inside the locker and he forgot the password. Without
glasses he can't help her. The password is hidden in N integers i.e. $a[1], a[2], ..... a[N]$ 
written on his magical stick.The password is the maximum number of moves Fizza can perform, for any position $i$ such that 1 < = $i$ < = $N$ and integer $X$ is present at $i$-th
position. In one move she can perform one of the following operations ->
$(1)$  If ( $i$ + 1 < = $N$ ) she can go to position ($i$ + 1 ) if integer at ( $i$ + 1 )-th 
position is equal to $X$.
$(2)$ if ( $i$ + 2 < = $N$ ) she can go to position ($i$ + 2 ) if integer at ($i$ + 2)-th 
position is equal to $X$.
Fizza is a bit worried about her beauty so she can't focus on the problem but she asked for 
your help to find the password.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase consists of  two lines of input.
- Input $N$.
- Input $N$ integers . 

-----Output:-----
For each testcase, output in a single line Maximum number of moves.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 10^5$
- $1 \leq a[i] \leq 2*10^5$

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

-----Sample Output:-----
1
2
0

-----EXPLANATION:-----
In the first case, integers at position 1 and 3 are the same and at alternate positions.
In the second case, integers at position 1, 2, 4 follow the conditions.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
When users post an update on social media,such as a URL, image, status update etc., other users in their network are able to view this new post on their news feed. Users can also see exactly when the post was published, i.e, how many hours, minutes or seconds ago.
Since sometimes posts are published and viewed in different time zones, this can be confusing. You are given two timestamps of one such post that a user can see on his newsfeed in the following format:
Day dd Mon yyyy hh:mm:ss +xxxx
Here +xxxx represents the time zone. Your task is to print the absolute difference (in seconds) between them.

=====Input Format=====
The first line contains T, the number of tescases.
Each testcase contains 2 lines, representing time t_1 and time t_2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Department of economic development of IT City created a model of city development till year 2100.

To prepare report about growth perspectives it is required to get growth estimates from the model.

To get the growth estimates it is required to solve a quadratic equation. Since the Department of economic development of IT City creates realistic models only, that quadratic equation has a solution, moreover there are exactly two different real roots.

The greater of these roots corresponds to the optimistic scenario, the smaller one corresponds to the pessimistic one. Help to get these estimates, first the optimistic, then the pessimistic one.

Input

The only line of the input contains three integers a, b, c ( - 1000 ≤ a, b, c ≤ 1000) — the coefficients of ax2 + bx + c = 0 equation.

Output

In the first line output the greater of the equation roots, in the second line output the smaller one. Absolute or relative error should not be greater than 10 - 6.

Examples

Input

1 30 200


Output

-10.000000000000000
-20.000000000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Stack is a container of elements that are inserted and deleted according to LIFO (Last In First Out).

For $n$ stack $S_i$ ($i = 0, 1, ..., n-1$), perform a sequence of the following operations.

* push($t$, $x$): Insert an integer $x$ to $S_t$.
* top($t$): Report the value which should be deleted next from $S_t$. If $S_t$ is empty, do nothing.
* pop($t$): Delete an element from $S_t$. If $S_t$ is empty, do nothing.



In the initial state, all stacks are empty.

Constraints

* $1 \leq n \leq 1,000$
* $1 \leq q \leq 200,000$
* $-1,000,000,000 \leq x \leq 1,000,000,000$

Input

The input is given in the following format.


$n \; q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given by


0 $t$ $x$


or


1 $t$


or


2 $t$


where the first digits 0, 1 and 2 represent push, top and pop operations respectively.

Output

For each top operation, print an integer in a line.

Example

Input

3 9
0 0 1
0 0 2
0 0 3
0 2 4
0 2 5
1 0
1 2
2 0
1 0


Output

3
5
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S which contains only small letters. The task is to make a square matrix from string S. Then perform the following operations.
1. In each column delete the characters which occur more than one.
2. Column-wise sort the remaining characters in order abcd....wxyz. But print them in order azbycxdw....  
For example, after operation 1 if the remaining characters in a column are cedjki then after sorting they become cdeijk , now when printed in the given order the output will be ckdjei. If there's no character remaining Print 0.
Note: Length of the Input String is always a Perfect Square.
 
Example 1:
Input:
S = "adgkbdhlceilcfjm"
Output:
abefgjhikm
Explanation:
Matrix will be
a d g k
b d h l
c e i  l
c f  j m
In 1st column 'c', in 2nd column 'd' and in
4th column 'l' has occurred more than once.
So after deleting them and sorting the
remaining characters the matrix become 
   a - g  k
   b - h  -
   - e i   -
   - f  j  m 
So after operation 2 we get 'ab' from 1st
column, 'ef' from 2nd column, 'gjhi' from
3rd column and 'km' from 4th column. Appending
all of them we get the output as  "abefgjhikm".
Example 2:
Input:
S = "abcabcabc"
Output:
0
Explanation:
Matrix will be
a b c
a b c
a b c
So, There will be no letters remaining
and the output will be 0. 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function matrixGame() which takes a String S and returns the answer.
 
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
 
Constraints
1 <= |S| <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp really likes writing the word "kotlin". He wrote this word several times in a row without spaces. For example, he could write the string like "kotlinkotlinkotlinkotlin".

Polycarp sliced (cut) the written string into n pieces and mixed them. As a result, he has n strings s_1, s_2, ..., s_n and he can arrange them in the right order, concatenate (join) all of them and get a string like "kotlinkotlin...kotlin".

Help Polycarp to find the right order of strings s_1, s_2, ..., s_n, so that if he writes the strings in this order, he will get the word "kotlin" or the sequence of this word.

Pay attention that you must use all given strings and you must use each string only once.

Input

The first line of the input contains one integer n (1 ≤ n ≤ 10^5) — the number of Polycarp's strings. Next lines of the input contain n Polycarp's strings.

Total sum of their lengths doesn't exceed 3⋅10^5. It's guaranteed that there is the right order of arrangement the strings that if you concatenate them into one string, you will get some non-empty sequence of the word "kotlin".

Output

Print n different integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n), where p_i is an index of the string that should be the i-th in a required concatenation. In other words, the result of concatenation s_{p_1}+s_{p_2}+...+s_{p_n} must be in the form "kotlinkotlin...kotlin". If there are many solutions, print any of them.

Examples

Input


2
lin
kot


Output


2 1 

Input


4
linkotlinkotlinkotl
kotlin
in
kot


Output


2 4 1 3 

Input


8
i
n
tlin
o
ko
t
k
l


Output


7 4 3 5 6 8 1 2 

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
One rainy gloomy evening when all modules hid in the nearby cafes to drink hot energetic cocktails, the Hexadecimal virus decided to fly over the Mainframe to look for a Great Idea. And she has found one!

Why not make her own Codeforces, with blackjack and other really cool stuff? Many people will surely be willing to visit this splendid shrine of high culture.

In Mainframe a standard pack of 52 cards is used to play blackjack. The pack contains cards of 13 values: 2, 3, 4, 5, 6, 7, 8, 9, 10, jacks, queens, kings and aces. Each value also exists in one of four suits: hearts, diamonds, clubs and spades. Also, each card earns some value in points assigned to it: cards with value from two to ten earn from 2 to 10 points, correspondingly. An ace can either earn 1 or 11, whatever the player wishes. The picture cards (king, queen and jack) earn 10 points. The number of points a card earns does not depend on the suit. The rules of the game are very simple. The player gets two cards, if the sum of points of those cards equals *n*, then the player wins, otherwise the player loses.

The player has already got the first card, it's the queen of spades. To evaluate chances for victory, you should determine how many ways there are to get the second card so that the sum of points exactly equals *n*.

Input Specification:
The only line contains *n* (1<=≤<=*n*<=≤<=25) — the required sum of points.

Output Specification:
Print the numbers of ways to get the second card in the required way if the first card is the queen of spades.

Demo Input:
['12\n', '20\n', '10\n']

Demo Output:
['4', '15', '0']

Note:
In the first sample only four two's of different suits can earn the required sum of points.

In the second sample we can use all tens, jacks, queens and kings; overall it's 15 cards, as the queen of spades (as any other card) is only present once in the pack of cards and it's already in use.

In the third sample there is no card, that would add a zero to the current ten points.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The employees of the R1 company often spend time together: they watch football, they go camping, they solve contests. So, it's no big deal that sometimes someone pays for someone else.

Today is the day of giving out money rewards. The R1 company CEO will invite employees into his office one by one, rewarding each one for the hard work this month. The CEO knows who owes money to whom. And he also understands that if he invites person x to his office for a reward, and then immediately invite person y, who has lent some money to person x, then they can meet. Of course, in such a situation, the joy of person x from his brand new money reward will be much less. Therefore, the R1 CEO decided to invite the staff in such an order that the described situation will not happen for any pair of employees invited one after another.

However, there are a lot of employees in the company, and the CEO doesn't have a lot of time. Therefore, the task has been assigned to you. Given the debt relationships between all the employees, determine in which order they should be invited to the office of the R1 company CEO, or determine that the described order does not exist.

Input

The first line contains space-separated integers n and m <image> — the number of employees in R1 and the number of debt relations. Each of the following m lines contains two space-separated integers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi), these integers indicate that the person number ai owes money to a person a number bi. Assume that all the employees are numbered from 1 to n.

It is guaranteed that each pair of people p, q is mentioned in the input data at most once. In particular, the input data will not contain pairs p, q and q, p simultaneously.

Output

Print -1 if the described order does not exist. Otherwise, print the permutation of n distinct integers. The first number should denote the number of the person who goes to the CEO office first, the second number denote the person who goes second and so on.

If there are multiple correct orders, you are allowed to print any of them.

Examples

Input

2 1
1 2


Output

2 1 


Input

3 3
1 2
2 3
3 1


Output

2 1 3 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer N.

Find a triple of positive integers h, n and w such that 4/N = 1/h + 1/n + 1/w.

If there are multiple solutions, any of them will be accepted.

Constraints

* It is guaranteed that, for the given integer N, there exists a solution such that h,n,w \leq 3500.

Inputs

Input is given from Standard Input in the following format:


N


Outputs

Print a triple of positive integers h, n and w that satisfies the condition, in the following format:


h n w

Examples

Input

2


Output

1 2 2


Input

3485


Output

872 1012974 1539173474040


Input

4664


Output

3498 3498 3498

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

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
The Olympic Games in Bercouver are in full swing now. Here everyone has their own objectives: sportsmen compete for medals, and sport commentators compete for more convenient positions to give a running commentary. Today the main sport events take place at three round stadiums, and the commentator's objective is to choose the best point of observation, that is to say the point from where all the three stadiums can be observed. As all the sport competitions are of the same importance, the stadiums should be observed at the same angle. If the number of points meeting the conditions is more than one, the point with the maximum angle of observation is prefered. 

Would you, please, help the famous Berland commentator G. Berniev to find the best point of observation. It should be noted, that the stadiums do not hide each other, the commentator can easily see one stadium through the other.

Input Specification:
The input data consists of three lines, each of them describes the position of one stadium. The lines have the format *x*,<=<=*y*,<=<=*r*, where (*x*,<=*y*) are the coordinates of the stadium's center (<=-<=<=103<=≤<=*x*,<=<=*y*<=≤<=103), and *r* (1<=≤<=*r*<=<=≤<=103) is its radius. All the numbers in the input data are integer, stadiums do not have common points, and their centers are not on the same line.

Output Specification:
Print the coordinates of the required point with five digits after the decimal point. If there is no answer meeting the conditions, the program shouldn't print anything. The output data should be left blank.

Demo Input:
['0 0 10\n60 0 10\n30 30 10\n']

Demo Output:
['30.00000 0.00000\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Energy resources were getting depleted on the planet Kepler and Xenny was the head of the Energy Saving Committee.

Xenny was in-charge of a large piece of land, which was square in shape. The land was of size N x N. He placed square-shaped solar cells (1 x 1) on the piece of land uniformly, all over the land. Just when Xenny finished placing all solar cells, each cell received a power of K units.

Xenny worked for D days as in-charge. On each day, he performed A actions. 

In each action, he either measured the total solar power received by a set of solar cells (sub-rectangle) or set the orientation of a single cell such that its reception power became Z times the previous power.

Input:
First line contains D, the no. of days.
For each day, first line contains N and K - one side of the square piece land and initial value of reception power of each cell.
Second line contains A - no. of actions.  

Actions: 
 1. m x1 y1 x2 y2 - Measure solar powerful from (x1, y1) to (x2, y2).
 2. s x y Z- Set rotation of single cell (x, y), such that its reception power gets multiplied by a factor of Z.

Output:
Print the total reception power for every action in which "measurement" is done, modulo 10^9 + 7.  

Constraints:
1 ≤ D ≤ 10
1 ≤ N ≤ 1000
1 ≤ K ≤ 100
1 ≤ A ≤ 10^4
1 ≤ x1, y1, x2, y2 ≤ N
x1 ≤ x2 and y1 ≤ y2
1 ≤ Z ≤ 100
(Note: x1, y1, x2, y2 are 1-indexed)

SAMPLE INPUT
1
3 1
3
m 1 1 1 3
s 1 2 3
m 1 1 1 3

SAMPLE OUTPUT
3
5

Explanation

Initial powers of solar cells:

1 1 1
1 1 1
1 1 1

Measured power of cells from (1, 1) to (1, 3) = 1 + 1 + 1 = 3

After setting orientation of (1, 2):

1 3 1
1 1 1
1 1 1

Measure power of cells from (1, 1) to (1, 3) = 1 + 3 + 1 = 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A graph is called planar, if it can be drawn in such a way that its edges intersect only at their vertexes.

An articulation point is such a vertex of an undirected graph, that when removed increases the number of connected components of the graph.

A bridge is such an edge of an undirected graph, that when removed increases the number of connected components of the graph.

You've got a connected undirected planar graph consisting of n vertexes, numbered from 1 to n, drawn on the plane. The graph has no bridges, articulation points, loops and multiple edges. You are also given q queries. Each query is a cycle in the graph. The query response is the number of graph vertexes, which (if you draw a graph and the cycle on the plane) are located either inside the cycle, or on it. Write a program that, given the graph and the queries, will answer each query.

Input

The first line contains two space-separated integers n and m (3 ≤ n, m ≤ 105) — the number of vertexes and edges of the graph. Next m lines contain the edges of the graph: the i-th line contains two space-separated integers ui and vi (1 ≤ ui, vi ≤ n) — the numbers of vertexes, connecting the i-th edge. The next n lines contain the positions of the planar graph vertexes on the plane: the i-th line contains a pair of space-separated integers xi and yi (|xi|, |yi| ≤ 109) — the coordinates of the i-th vertex of the graph on the plane. 

The next line contains integer q (1 ≤ q ≤ 105) — the number of queries. Then follow q lines that describe the queries: the i-th line contains the sequence of space-separated integers ki, a1, a2, ..., aki (1 ≤ aj ≤ n; ki > 2), where ki is the cycle length in the i-th query, aj are numbers of the vertexes that form a cycle. The numbers of vertexes in the cycle are given in the clockwise or counterclockwise order. The given cycles are simple, that is they cannot go through a graph vertex more than once. The total length of all cycles in all queries does not exceed 105.

It is guaranteed that the given graph contains no bridges, articulation points, loops and multiple edges. It is guaranteed that the edge segments can have common points only at the graph's vertexes.

Output

For each query print a single integer — the number of vertexes inside the cycle or on it. Print the answers in the order, in which the queries follow in the input. Separate the numbers by spaces.

Examples

Input

3 3
1 2
2 3
3 1
0 0
1 0
0 1
1
3 1 2 3


Output

3


Input

5 8
1 2
2 3
3 4
4 1
1 5
2 5
3 5
4 5
0 0
2 0
2 2
0 2
1 1
1
4 1 2 3 4


Output

5


Input

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


Output

3
3
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has a rectangular plate of length  N cm  and width M cm. He wants to make a wireframe around the plate. The wireframe costs X rupees per cm. 

Determine the cost Chef needs to incur to buy the wireframe.

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

- First line will contain T, the number of test cases. Then the test cases follow.
- Each test case consists of a single line of input, containing three space-separated integers N,M, and X — the length of the plate, width of the plate, and the cost of frame per cm.

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

For each test case, output in a single line, the price Chef needs to pay for the wireframe.

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

$1 ≤ T ≤ 1000$
$1 ≤ N,M,X ≤ 1000 $

----- Sample Input 1 ------ 
3
10 10 10
23 3 12
1000 1000 1000

----- Sample Output 1 ------ 
400
624
4000000
----- explanation 1 ------ 
Test case $1$: The total length of the frame is $2\cdot 10 + 2\cdot 10 = 40$ cms. Since the cost is $10$ per cm, the total cost would be $10 \cdot 40 = 400$.

Test case $2$: The total length of the frame is $2\cdot 23 + 2\cdot 3 = 52$ cms. Since the cost is $12$ per cm, the total cost would be $52 \cdot 12 = 624$.

Test case $3$: The total length of the frame is $2\cdot 1000 + 2\cdot 1000 = 4000$ cms. Since the cost is $1000$ per cm, the total cost would be $4000 \cdot 1000 = 4000000$.

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