vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Chef has planned that he will drink exactly X liters of tea daily. He has an empty jar having a capacity of Y liters.

Chef can visit the tea shop to refill the jar. In each refill, the jar is completely filled to the brim and Chef is charged Z rupees.

Chef wonders what is the minimum amount of money he has to pay for drinking exactly X liters of tea daily.

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

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single line of input, three space-separated integers X, Y, and Z denoting the amount of tea Chef has to drink daily, the capacity of his jar and the cost of refilling his jar.

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

For each test case, output in a single line, the minimum amount Chef has to pay.

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

$1 ≤ T ≤ 1000$
$1 ≤ X, Y, Z ≤ 100$

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

----- Sample Output 1 ------ 
3
6
2
15

----- explanation 1 ------ 
Test case $1$: Chef can get his jar refilled once and drink $3$ liters of tea, which will cost him $3$ rupees in total. 

Test case $2$: Chef needs to refill his jar twice to get $3\cdot 2 = 6$ liters of tea, which will cost him $3\cdot 2 = 6$ rupees in total.

Test case $3$: Chef can refill his jar once and drink exactly $5$ liters out of the $7$ liters. This will cost him $2$ rupees.

Test case $4$: Chef can refill his jar twice and drink $4\cdot 2 = 8$ liters of tea. He needs to have one more refill, but this time he would drink only $1$ liter tea from the jar. Thus the total tea he drinks is $4+4+1 = 9$ liters. He made $3$ refills in total costing him $5\cdot 3 = 15$ rupees.

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

There was a person who loved dictionaries. They love to make their own dictionaries. So you decided to add the ability to customize their dictionaries.

Problem

First, there is an empty dictionary that doesn't contain any words. Given N strings Sid and Q queries. Each query is given with a query type k and an id pointing to a string. There are three types of queries:

* Add Sid to the dictionary when k = 1.
* Delete Sid from the dictionary when k = 2.
* When k = 3, Sid is included in the substring from the beginning among the character strings added to the dictionary, and the id of the smallest character string in the dictionary order is output. If not, output -1.



I want you to write a program that answers each query.

Note: Due to the large input size, we recommend a format that supports high-speed input.

Constraints

* All strings are different.
* The total length of N strings Sid does not exceed 106.
* There is no input that re-adds a string that has already been added to the dictionary.
* There is no input to delete a string that has not been added to the dictionary.
* The given character string contains only lowercase letters.
* 1 ≤ N ≤ 105
* 1 ≤ id ≤ N
* 1 ≤ Q ≤ 105
* 1 ≤ | Sid | ≤ 105 (where | s | represents the length of the string s.)

Input

The input is given in the following format.


N
S1
S2
..
..
..
SN
Q
k1 id1
k2 id2
..
..
..
kQ idQ


The first line is given one integer N. From the second line to the N + 1 line, N character strings Sid are given. The number Q of queries is given in the N + 2nd line, and the following Q lines are given k indicating the type of each query and id indicating a character string.

Output

Print the answer on one line for each query.

Examples

Input

3
apple
app
banana
9
1 1
3 1
3 2
3 3
2 1
1 2
3 1
3 2
3 3


Output

1
1
-1
-1
2
-1


Input

7
aaaab
aaa
aaaa
aaaaaabc
abbbbbc
ab
abbb
13
1 1
3 2
1 4
3 2
1 3
3 2
2 3
3 3
1 5
1 7
3 6
2 5
3 6


Output

1
4
3
4
7
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
n children are standing in a circle and playing a game. Children's numbers in clockwise order form a permutation a1, a2, ..., an of length n. It is an integer sequence such that each integer from 1 to n appears exactly once in it.

The game consists of m steps. On each step the current leader with index i counts out ai people in clockwise order, starting from the next person. The last one to be pointed at by the leader becomes the new leader.

You are given numbers l1, l2, ..., lm — indices of leaders in the beginning of each step. Child with number l1 is the first leader in the game. 

Write a program which will restore a possible permutation a1, a2, ..., an. If there are multiple solutions then print any of them. If there is no solution then print -1.

Input

The first line contains two integer numbers n, m (1 ≤ n, m ≤ 100).

The second line contains m integer numbers l1, l2, ..., lm (1 ≤ li ≤ n) — indices of leaders in the beginning of each step.

Output

Print such permutation of n numbers a1, a2, ..., an that leaders in the game will be exactly l1, l2, ..., lm if all the rules are followed. If there are multiple solutions print any of them. 

If there is no permutation which satisfies all described conditions print -1.

Examples

Input

4 5
2 3 1 4 4


Output

3 1 2 4 


Input

3 3
3 1 2


Output

-1

Note

Let's follow leadership in the first example: 

  * Child 2 starts. 
  * Leadership goes from 2 to 2 + a2 = 3. 
  * Leadership goes from 3 to 3 + a3 = 5. As it's greater than 4, it's going in a circle to 1. 
  * Leadership goes from 1 to 1 + a1 = 4. 
  * Leadership goes from 4 to 4 + a4 = 8. Thus in circle it still remains at 4. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kate has finally calmed down and decides to forgive Little Deepu, but she won't forgive him just like that. She agrees to forgive him on the grounds that he can solve a mathematical question for her. 
She gives Deepu a large number N and a prime number P and asks him to calculate ((3*N)! / (3!^N) )%P.Your task is to help Little Deepu get back together with Kate.

Input
First line contains number of test cases T.
Next T lines contain two integers N and P, where P is a prime.  

Output
For each test case output the result ( (3*N)! / (3!)^N ) % P.  

Constraints:
1 ≤ T ≤ 10000
1 ≤ N ≤ 333333333
1 ≤ P ≤ 1000000000
1 ≤ abs(3*N-P) ≤ 1000  

SAMPLE INPUT
2
3 11
2 11

SAMPLE OUTPUT
8
9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have the following sequence:
```python
f(0) = 0
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 4;
f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4) + f(n-5);
```

Your task is to give the number of total values for the odd terms of the sequence  up to the n-th term (included). (The number n (of n-th term) will be given as a positive integer)

The values 1 (one) is the only that is duplicated in the sequence and should be counted only once.

E.g. 
```
count_odd_pentaFib(5) -----> 1 # because the terms up to 5 are: 0, 1, 1, 2, 4, 8 (only 1 is odd and counted once)
```
Other examples:
```
 count_odd_pentaFib(10) ------> 3 #because the odds terms are: [1, 1, 31, 61] (three different values)

count_odd_pentaFib(15) ------> 5 # beacause the odd terms are: [1, 1, 31, 61, 1793, 3525] (five different values)
```
Good luck !!

(Your code should be fast. Many moderate high values will be waiting to test it.)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the following 6 digit number:

```
283910
```

`91` is the greatest sequence of 2 consecutive digits.

In the following 10 digit number:
```
1234567890
```

`67890` is the greatest sequence of 5 consecutive digits.

Complete the solution so that it returns the greatest sequence of five consecutive digits found within the number given. The number will be passed in as a string of only digits. It should return a five digit integer. The number passed may be as large as 1000 digits. 

*Adapted from ProjectEuler.net*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers, $a$ and $b$. You want to transform $a$ to $b$ by performing a sequence of operations. You can only perform the following operations:
 - Divide $a$ by two (only if $a$ is even)
 - Add one to $a$

What is the minimum number of these operations you need to transform $a$ into $b$?

-----Input-----
The single line of input contains two space-separated integers $a$ and $b$ ($1\le a,b \le 10^9$). You want to transform $a$ into $b$ using only the operations given above.

-----Output-----
Output a single integer, which is the minimum number of the given operations needed to transform $a$ into $b$.

-----Examples-----
Sample Input:
103 27
Sample Output:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A cellular provider has installed $n$ towers to support their network. Each tower provides coverage in a $1\text { km}$ radius, and no two towers are closer than $1\text { km}$ to each other. The coverage region of this network is therefore the set of all points that are no more than $1\text { km}$ away from at least one tower. The provider wants as much of this region as possible to be connected, in the sense that a user at any point within a connected subregion can travel to any other point within the connected subregion without having to exit the subregion. Their current installation of towers may or may not already form a single connected region, but they have the resources to build one more tower wherever they want, including within $1\text { km}$ of an existing tower. Given that the provider is able to build one more tower, what is the maximum number of towers (including the new one) that can be included within a single connected subregion of coverage?

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input consists of a single integer $n$ ($1 \le n \le 5000$) denoting the number of existing towers. Next follow $n$ lines, each with $2$ space-separated floating-point numbers $x$ and $y$ ($0 \le x, y \le 100000$, at most $5$ digits after the decimal point), denoting the location of a tower in km. It is guaranteed that the optimal number of towers will not change even if the coverage radius of all the towers is increased or decreased by $10^{-6}\text { km}$.

-----Output-----
Output a single integer, denoting the maximum number of towers that can be within a single connected subregion of the network after installing one additional tower.

-----Examples-----
Sample Input:
5
1.0 1.0
3.1 1.0
1.0 3.1
3.1 3.1
4.2 3.1
Sample Output:
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s which contains lowercase english letters and dot sign (.) (e.g:   abc.d.ee.g). Your task is to replace substring '..' with a substring '.' in the given string i.e the string should not contain 2 consecutive dot signs. You need to calculate the no. of replacements required for this task.

First line contains two integers L denoting length of string and N denoting no. of queries on the string. Second line of input contains string s
Each of the next N lines contains 2 inputs    k(integer) and p(lowercase letter/dot sign).
Your task is to replace k th letter in given string with given letter p and count the replacements.
For the next query use the string modified in previous query.

SAMPLE INPUT
4 4
.cc.
2 .
3 .
2 a
1 a

SAMPLE OUTPUT
1
3
1
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andy is going holiday shopping and needs to buy several Christmas trees. At the store, there is a row of Christmas trees of various heights. Andy is only allowed to buy trees that are next to each other, i.e. trees that are contiguous within the row. He also wants to make sure that the shortest tree he buys and the tallest tree he buys are as close in height as possible. What is the smallest height difference he can get given the constraints?

-----Input-----
The input consists of two lines. The first line contains two integers $n$ and $k$ ($2 \leq k \leq n \leq 200000$), representing the number of trees in the row and the number of trees Andy needs to buy, respectively. The second line consists of $n$ integers $a_1, a_2, \ldots , a_ n$ where $1 \leq a_ i \leq 100$, representing the height of each tree.

-----Output-----
Output the minimum height difference between the shortest and tallest trees of any contiguous subrange of $k$ trees.

-----Examples-----
Sample Input:
10 2
1 3 5 7 9 11 13 15 17 16
Sample Output:
1

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

A string, $\boldsymbol{\mathrm{~S~}}$, of length $n$ where $s=c_0c_1\ldots c_{n-1}$.
An integer, $\boldsymbol{\mbox{k}}$, where $\boldsymbol{\mbox{k}}$ is a factor of $n$.

We can split $\boldsymbol{\mathrm{~S~}}$ into $\frac{n}{k}$ substrings where each subtring, $t_i$, consists of a contiguous block of $\boldsymbol{\mbox{k}}$ characters in $\boldsymbol{\mathrm{~S~}}$. Then, use each $t_i$ to create string $u_i$ such that:

The characters in $u_i$ are a subsequence of the characters in $t_i$. 
Any repeat occurrence of a character is removed from the string such that each character in $u_i$ occurs exactly once. In other words, if the character at some index $j$ in $t_i$ occurs at a previous index $\lt j$ in $t_i$, then do not include the character in string $u_i$.

Given $\boldsymbol{\mathrm{~S~}}$ and $\boldsymbol{\mbox{k}}$, print $\frac{n}{k}$ lines where each line $\boldsymbol{i}$ denotes string $u_i$.  

Example 

$s=\text{'AAABCADDE'}$ 

$k=3$  

There are three substrings of length $3$ to consider: 'AAA', 'BCA' and 'DDE'.  The first substring is all 'A' characters, so $u_1=\text{'A'}$.  The second substring has all distinct characters, so $u_2=\text{'BCA'}$.  The third substring has $2$ different characters, so $u_3=\text{'DE'}$.  Note that a subsequence maintains the original order of characters encountered.  The order of characters in each subsequence shown is important.  

Function Description  

Complete the merge_the_tools function in the editor below.  

merge_the_tools has the following parameters:  

string s: the string to analyze  
int k: the size of substrings to analyze  

Prints  

Print each subsequence on a new line.  There will be $\frac{n}{k}$ of them.  No return value is expected.  

Input Format

The first line contains a single string, $\boldsymbol{\mathrm{~S~}}$. 

The second line contains an integer, $\boldsymbol{\mbox{k}}$, the length of each substring.

Constraints

$1\leq n\leq10^4$, where $n$ is the length of $\boldsymbol{\mathrm{~S~}}$
$1\leq k\leq n$ 
It is guaranteed that $n$ is a multiple of $\boldsymbol{\mbox{k}}$. 

Sample Input
STDIN       Function
-----       --------
AABCAAADA   s = 'AABCAAADA'
3           k = 3

Sample Output
AB
CA
AD

Explanation

Split $\boldsymbol{\mathrm{~S~}}$ into $\frac{n}{k}=\frac{9}{3}=3$ equal parts of length $k=3$. Convert each $t_i$ to $u_i$ by removing any subsequent occurrences of non-distinct characters in $t_i$:

$t_0=\textsf{"AAB"}\to u_0=\textsf{"AB"}$
$t_1=\text{"CAA}\rightarrow u_1=\text{"CA}\text{"}$
$t_2=\text{"ADA}\text{"}\rightarrow u_2=\text{"AD}\text{"}$

Print each $u_i$ on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The ABC number of a string T is the number of triples of integers (i, j, k) that satisfy all of the following conditions:
 - 1 ≤ i < j < k ≤ |T| (|T| is the length of T.)
 - T_i = A (T_i is the i-th character of T from the beginning.)
 - T_j = B
 - T_k = C
For example, when T = ABCBC, there are three triples of integers (i, j, k) that satisfy the conditions: (1, 2, 3), (1, 2, 5), (1, 4, 5). Thus, the ABC number of T is 3.
You are given a string S. Each character of S is A, B, C or ?.
Let Q be the number of occurrences of ? in S. We can make 3^Q strings by replacing each occurrence of ? in S with A, B or C. Find the sum of the ABC numbers of all these strings.
This sum can be extremely large, so print the sum modulo 10^9 + 7.

-----Constraints-----
 - 3 ≤ |S| ≤ 10^5
 - Each character of S is A, B, C or ?.

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print the sum of the ABC numbers of all the 3^Q strings, modulo 10^9 + 7.

-----Sample Input-----
A??C

-----Sample Output-----
8

In this case, Q = 2, and we can make 3^Q = 9 strings by by replacing each occurrence of ? with A, B or C. The ABC number of each of these strings is as follows:
 - AAAC: 0
 - AABC: 2
 - AACC: 0
 - ABAC: 1
 - ABBC: 2
 - ABCC: 2
 - ACAC: 0
 - ACBC: 1
 - ACCC: 0
The sum of these is 0 + 2 + 0 + 1 + 2 + 2 + 0 + 1 + 0 = 8, so we print 8 modulo 10^9 + 7, that is, 8.

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

Given the formula $ S $ of length $ N $. The formula is in the format shown in BNF below.


<expr> :: = <number> | <expr> <op> <expr>

<op> :: = ‘^’ | ‘&’ | ‘|’



<number> represents an integer greater than or equal to $ 0 $ and less than or equal to $ 2 ^ {31} -1 $.

The operators ‘^’ ‘&’ ‘|’ represent exclusive OR, AND, and OR, respectively. The precedence of operators is as follows.

High ‘^’> ‘&’> ‘|’ Low

$ Q $ intervals $ [i, j] $ are given. Output the calculation result of $ S_i, \ dots, S_j $.

It is guaranteed that the formulas $ S_i, \ dots, S_j $ are in the format shown by the above BNF. Also, the formula does not contain zero-padded values.



output

Output the calculation result of $ S_i, \ dots, S_j $. Also, output a line break at the end.

Example

Input

7
9^2&1|2
4
0 6
0 2
2 6
4 4


Output

3
11
2
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this kata you have to correctly return who is the "survivor", ie: the last element of a Josephus permutation.

Basically you have to assume that n people are put into a circle and that they are eliminated in steps of k elements, like this:

```
josephus_survivor(7,3) => means 7 people in a circle;
one every 3 is eliminated until one remains
[1,2,3,4,5,6,7] - initial sequence
[1,2,4,5,6,7] => 3 is counted out
[1,2,4,5,7] => 6 is counted out
[1,4,5,7] => 2 is counted out
[1,4,5] => 7 is counted out
[1,4] => 5 is counted out
[4] => 1 counted out, 4 is the last element - the survivor!
```

The above link about the "base" kata description will give you a more thorough insight about the origin of this kind of permutation, but basically that's all that there is to know to solve this kata.

**Notes and tips:** using the solution to the other kata to check your function may be helpful, but as much larger numbers will be used, using an array/list to compute the number of the survivor may be too slow; you may assume that both n and k will always be >=1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese. 

In a rooted tree, the  (or LCA for short) of two vertices u and v is defined as the lowest vertex that is ancestor of both that two vertices.

Given a tree of N vertices, you need to answer the question of the form "r u v" which means if the root of the tree is at r then what is LCA of u and v.
 
------ Input ------ 

The first line contains a single integer N. Each line in the next N - 1 lines contains a pair of integer u and v representing a edge between this two vertices.

The next line contains a single integer Q which is the number of the queries. Each line in the next Q lines contains three integers  r, u, v representing a query.
 
------ Output ------ 

For each query, write out the answer on a single line.

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

20 points:

1 ≤ N, Q ≤ 100

40 points:

1 ≤ N, Q ≤ 10^{5}
There is less than 10 unique value of r in all queries

40 points:

1 ≤ N, Q ≤ 2 × 10^{5}

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

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

Output:
1
2

------ Explanation ------ 

"1 4 2": if 1 is the root, it is parent of both 2 and 4 so LCA of 2 and 4 is 1.
"2 4 2": the root of the tree is at 2, according to the definition, LCA of any vertex with 2 is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:

if x is even then x = x / 2
if x is odd then x = 3 * x + 1

For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1).
Given three integers lo, hi and k. The task is to sort all integers in the interval [lo, hi] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.
Return the k-th integer in the range [lo, hi] sorted by the power value.
Notice that for any integer x (lo <= x <= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in 32 bit signed integer.
 
Example 1:
Input: lo = 12, hi = 15, k = 2
Output: 13
Explanation: The power of 12 is 9 (12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)
The power of 13 is 9
The power of 14 is 17
The power of 15 is 17
The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13.
Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15.

Example 2:
Input: lo = 1, hi = 1, k = 1
Output: 1

Example 3:
Input: lo = 7, hi = 11, k = 4
Output: 7
Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14].
The interval sorted by power is [8, 10, 11, 7, 9].
The fourth number in the sorted array is 7.

Example 4:
Input: lo = 10, hi = 20, k = 5
Output: 13

Example 5:
Input: lo = 1, hi = 1000, k = 777
Output: 570

 
Constraints:

1 <= lo <= hi <= 1000
1 <= k <= hi - lo + 1

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