vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
On a certain meeting of a ruling party "A" minister Pavel suggested to improve the sewer system and to create a new pipe in the city.

The city is an n × m rectangular squared field. Each square of the field is either empty (then the pipe can go in it), or occupied (the pipe cannot go in such square). Empty squares are denoted by character '.', occupied squares are denoted by character '#'.

The pipe must meet the following criteria:  the pipe is a polyline of width 1,  the pipe goes in empty squares,  the pipe starts from the edge of the field, but not from a corner square,  the pipe ends at the edge of the field but not in a corner square,  the pipe has at most 2 turns (90 degrees),  the border squares of the field must share exactly two squares with the pipe,  if the pipe looks like a single segment, then the end points of the pipe must lie on distinct edges of the field,  for each non-border square of the pipe there are exacly two side-adjacent squares that also belong to the pipe,  for each border square of the pipe there is exactly one side-adjacent cell that also belongs to the pipe. 

Here are some samples of allowed piping routes: 

           ....#            ....#            .*..#

           *****            ****.            .***.

           ..#..            ..#*.            ..#*.

           #...#            #..*#            #..*#

           .....            ...*.            ...*.



Here are some samples of forbidden piping routes: 

           .**.#            *...#            .*.*#

           .....            ****.            .*.*.

           ..#..            ..#*.            .*#*.

           #...#            #..*#            #*.*#

           .....            ...*.            .***.



In these samples the pipes are represented by characters ' * '.

You were asked to write a program that calculates the number of distinct ways to make exactly one pipe in the city. 

The two ways to make a pipe are considered distinct if they are distinct in at least one square.


-----Input-----

The first line of the input contains two integers n, m (2 ≤ n, m ≤ 2000) — the height and width of Berland map.

Each of the next n lines contains m characters — the map of the city. 

If the square of the map is marked by character '.', then the square is empty and the pipe can through it. 

If the square of the map is marked by character '#', then the square is full and the pipe can't through it.


-----Output-----

In the first line of the output print a single integer — the number of distinct ways to create a pipe.


-----Examples-----
Input
3 3
...
..#
...

Output
3
Input
4 2
..
..
..
..

Output
2

Input
4 5
#...#
#...#
###.#
###.#

Output
4


-----Note-----

In the first sample there are 3 ways to make a pipe (the squares of the pipe are marked by characters ' * '): 

       .*.        .*.        ...

       .*#        **#        **#

       .*.        ...        .*.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Duff is addicted to meat! Malek wants to keep her happy for n days. In order to be happy in i-th day, she needs to eat exactly a_{i} kilograms of meat. [Image] 

There is a big shop uptown and Malek wants to buy meat for her from there. In i-th day, they sell meat for p_{i} dollars per kilogram. Malek knows all numbers a_1, ..., a_{n} and p_1, ..., p_{n}. In each day, he can buy arbitrary amount of meat, also he can keep some meat he has for the future.

Malek is a little tired from cooking meat, so he asked for your help. Help him to minimize the total money he spends to keep Duff happy for n days. 


-----Input-----

The first line of input contains integer n (1 ≤ n ≤ 10^5), the number of days.

In the next n lines, i-th line contains two integers a_{i} and p_{i} (1 ≤ a_{i}, p_{i} ≤ 100), the amount of meat Duff needs and the cost of meat in that day.


-----Output-----

Print the minimum money needed to keep Duff happy for n days, in one line.


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

Output
10

Input
3
1 3
2 1
3 2

Output
8



-----Note-----

In the first sample case: An optimal way would be to buy 1 kg on the first day, 2 kg on the second day and 3 kg on the third day.

In the second sample case: An optimal way would be to buy 1 kg on the first day and 5 kg (needed meat for the second and third day) on the second day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Naming multiple files can be a pain sometimes.

#### Task:

Your job here is to create a function that will take three parameters, `fmt`, `nbr` and `start`, and create an array of `nbr` elements formatted according to `frm` with the starting index `start`. `fmt` will have `` inserted at various locations; this is where the file index number goes in each file. 

#### Description of edge cases:

1. If `nbr` is less than or equal to 0, or not whole, return an empty array.
2. If `fmt` does not contain `''`, just return an array with `nbr` elements that are all equal to `fmt`. 
3. If `start` is not an integer, return an empty array.

#### What each parameter looks like:

```python
type(frm) #=> str
  : "text_to_stay_constant_from_file_to_file "
type(nbr) #=> int
  : number_of_files
type(start) #=> int
  : index_no_of_first_file
type(name_file(frm, nbr, start)) #=> list
```

#### Some examples:

```python
name_file("IMG ", 4, 1)
  #=> ["IMG 1", "IMG 2", "IMG 3", "IMG 4"])
name_file("image #.jpg", 3, 7)
  #=> ["image #7.jpg", "image #8.jpg", "image #9.jpg"]
name_file("# #", 3, -2)
  #=> ["#-2 #-2", "#-1 #-1", "#0 #0"]
```

Also check out my other creations — [Elections: Weighted Average](https://www.codewars.com/kata/elections-weighted-average), [Identify Case](https://www.codewars.com/kata/identify-case), [Split Without Loss](https://www.codewars.com/kata/split-without-loss), [Adding Fractions](https://www.codewars.com/kata/adding-fractions),
[Random Integers](https://www.codewars.com/kata/random-integers), [Implement String#transpose](https://www.codewars.com/kata/implement-string-number-transpose), [Implement Array#transpose!](https://www.codewars.com/kata/implement-array-number-transpose), [Arrays and Procs #1](https://www.codewars.com/kata/arrays-and-procs-number-1), and [Arrays and Procs #2](https://www.codewars.com/kata/arrays-and-procs-number-2).

If you notice any issues or have any suggestions/comments whatsoever, please don't hesitate to mark an issue or just comment. Thanks!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are trains with 26 cars or less. Each vehicle has an identification code from lowercase a to z. No vehicle has the same symbol. However, the order in which the vehicles are connected is arbitrary. The conductor patrols the train. The conductor patrolls back and forth in the train, so he may pass through the same vehicle many times. However, all vehicles shall be patrolled at least once. In addition, the vehicle that starts the patrol and the vehicle that finishes the patrol is not necessarily the vehicle at the end of the train.

There is a patrol record of all the trains on which an Aru Shashou is on board. Create a program that outputs the formation of each train that can be seen from it from the lead car. The patrol record corresponds to one train per line. Each line consists of a string of lowercase letters separated by <-or->. <-Represents a move to a vehicle in front, and-> represents a move to a vehicle behind.

For example, a-> b <-a <-c means that vehicle a has moved to the vehicle behind b, b has moved to a ahead, and a has moved to c ahead. In this case, the train formation will be cab from the first car.



Input

The number of patrol records n (n ≤ 50) is given to the first line, and the character string si (half-width character string up to 1024 characters) representing the patrol record i is given to the following n lines.

Output

For patrol record i, output the character string indicating the formation of the train from the first car on the i-line.

Examples

Input

4
a->e->c->b->d
b


Output

aecbd
edacb
bacde
bcdae


Input

4
a->e->c->b->d
b<-c<-a<-d<-e
b->a->c<-a->c->d<-c<-a<-b->a->c->d->e<-d
a->e<-a<-d->a->e<-a<-d<-c->d->a<-d<-c<-b->c->d<-c


Output

aecbd
edacb
bacde
bcdae

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A country decides to build a palace.
In this country, the average temperature of a point at an elevation of x meters is T-x \times 0.006 degrees Celsius.
There are N places proposed for the place. The elevation of Place i is H_i meters.
Among them, Princess Joisino orders you to select the place whose average temperature is the closest to A degrees Celsius, and build the palace there.
Print the index of the place where the palace should be built.
It is guaranteed that the solution is unique.

-----Constraints-----
 - 1 \leq N \leq 1000
 - 0 \leq T \leq 50
 - -60 \leq A \leq T
 - 0 \leq H_i \leq 10^5
 - All values in input are integers.
 - The solution is unique.

-----Input-----
Input is given from Standard Input in the following format:
N
T A
H_1 H_2 ... H_N

-----Output-----
Print the index of the place where the palace should be built.

-----Sample Input-----
2
12 5
1000 2000

-----Sample Output-----
1

 - The average temperature of Place 1 is 12-1000 \times 0.006=6 degrees Celsius.
 - The average temperature of Place 2 is 12-2000 \times 0.006=0 degrees Celsius.
Thus, the palace should be built at Place 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Inna and Dima bought a table of size n × m in the shop. Each cell of the table contains a single letter: "D", "I", "M", "A".

Inna loves Dima, so she wants to go through his name as many times as possible as she moves through the table. For that, Inna acts as follows:

  initially, Inna chooses some cell of the table where letter "D" is written;  then Inna can move to some side-adjacent table cell that contains letter "I"; then from this cell she can go to one of the side-adjacent table cells that contains the written letter "M"; then she can go to a side-adjacent cell that contains letter "A". Then Inna assumes that she has gone through her sweetheart's name;  Inna's next move can be going to one of the side-adjacent table cells that contains letter "D" and then walk on through name DIMA in the similar manner. Inna never skips a letter. So, from the letter "D" she always goes to the letter "I", from the letter "I" she always goes the to letter "M", from the letter "M" she always goes to the letter "A", and from the letter "A" she always goes to the letter "D". 

Depending on the choice of the initial table cell, Inna can go through name DIMA either an infinite number of times or some positive finite number of times or she can't go through his name once. Help Inna find out what maximum number of times she can go through name DIMA.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 10^3). 

Then follow n lines that describe Inna and Dima's table. Each line contains m characters. Each character is one of the following four characters: "D", "I", "M", "A". 

Note that it is not guaranteed that the table contains at least one letter "D".


-----Output-----

If Inna cannot go through name DIMA once, print on a single line "Poor Dima!" without the quotes. If there is the infinite number of names DIMA Inna can go through, print "Poor Inna!" without the quotes. Otherwise print a single integer — the maximum number of times Inna can go through name DIMA.


-----Examples-----
Input
1 2
DI

Output
Poor Dima!

Input
2 2
MA
ID

Output
Poor Inna!

Input
5 5
DIMAD
DIMAI
DIMAM
DDMAA
AAMID

Output
4



-----Note-----

Notes to the samples:

In the first test sample, Inna cannot go through name DIMA a single time.

In the second test sample, Inna can go through the infinite number of words DIMA. For that, she should move in the clockwise direction starting from the lower right corner.

In the third test sample the best strategy is to start from the cell in the upper left corner of the table. Starting from this cell, Inna can go through name DIMA four times.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the following algorithm
order(arr, i) {
if length(arr) <= 1 {
return arr
}
l = []  
r = []
n = length(arr) - 1
for j in 0, 1, ..., n {
if ( (arr[j] modulo power(2,i+1))  < power(2,i) ) {
append arr[j] to l
}else{
append arr[j] to r
}
}
l = order(l, i + 1)
r = order(r, i + 1)
c = concatenate(l, r)
return c
}

Note that $concatenate(l, r)$ returns an array which is the array $l$, followed by the array $r$. Similarly $power(x,y)$ returns $x^y$.
Let $a$ be the array $a_0,a_1,a_2,a_3, \ldots,a_n$ where $a_j = j$ for each index $j$ and the last index $n = (2^p-1)$ for a fixed integer parameter $p$.  Given an integer $p$ and an index $idx$, your task is calculate the element at index $idx$ in the array returned by executing $order(a, 0)$.
For example, suppose $ p = 3$ and $idx = 3$.
- The initial array is $a = [0, 1, 2, 3, 4, 5, 6, 7]$.
- Executing $order(a, 0)$ first creates two new arrays $l == [0, 2, 4, 6]$ and $r == [1, 3, 5, 7]$.
- Next, $order(l, 1)$ and $order(r, 1)$ are executed.
- $order(l, 1)$, in turn, executes $order([0, 4], 2)$ and $order([2, 6], 2)$ which return $[0, 4]$ and $[2, 6]$, respectively. These are then concatenated, so $order(l, 1)$ returns $[0, 4, 2, 6]$.
- Similarly, $order(r, 1)$ returns $[1, 5, 3, 7]$.
- These two are concatenated as the final result, so the array returned by $order(a, 0)$ is $[0, 4, 2, 6, 1, 5, 3, 7]$.
So, if the input is $p = 3$, and $idx = 3$, the answer is $6$. If $p = 3$ and $idx = 7$, the answer should be $7$.

-----Input Format:-----
- The first line contains a single integer, $T$, which is the number of testcases. The description of each testcase follows.
- Each testcase is described by a single line with two integers: $p$ and $idx$, where $p$ is the parameter that determines the length of the array $a$ and $idx$ is the index at which you have to report the value in the output of $order(a, 0)$.

-----Output Format:-----
- You should print the answer in a new line for each testcase, which should be a single integer, the element at index $idx$ after executing $order(a, 0)$ for the array $a$ defined by the parameter $p$.

-----Constraints:-----
- $1 \leq T \leq 10$ 
- $1 \leq p \leq 50$
- $0 \leq idx \leq 2^p-1$

-----SUBTASKS:-----
- Subtask 1: 20% points : $1 \leq p \leq 20$
- Subtask 2: 80% points: Original constraints

-----Sample Input:-----
2
3 3
3 7

-----Sample Output:-----
6
7

-----Explanation:-----
Both the testcases have been explained in the problem statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given 2 integers $u$ and $v$, find the shortest array such that bitwise-xor of its elements is $u$, and the sum of its elements is $v$.


-----Input-----

The only line contains 2 integers $u$ and $v$ $(0 \le u,v \le 10^{18})$.


-----Output-----

If there's no array that satisfies the condition, print "-1". Otherwise:

The first line should contain one integer, $n$, representing the length of the desired array. The next line should contain $n$ positive integers, the array itself. If there are multiple possible answers, print any.


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

Output
2
3 1
Input
1 3

Output
3
1 1 1
Input
8 5

Output
-1
Input
0 0

Output
0


-----Note-----

In the first sample, $3\oplus 1 = 2$ and $3 + 1 = 4$. There is no valid array of smaller length.

Notice that in the fourth sample the array is empty.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sean is trying to save a large file to a USB flash drive. He has n USB flash drives with capacities equal to a_1, a_2, ..., a_{n} megabytes. The file size is equal to m megabytes. 

Find the minimum number of USB flash drives needed to write Sean's file, if he can split the file between drives.


-----Input-----

The first line contains positive integer n (1 ≤ n ≤ 100) — the number of USB flash drives.

The second line contains positive integer m (1 ≤ m ≤ 10^5) — the size of Sean's file.

Each of the next n lines contains positive integer a_{i} (1 ≤ a_{i} ≤ 1000) — the sizes of USB flash drives in megabytes.

It is guaranteed that the answer exists, i. e. the sum of all a_{i} is not less than m.


-----Output-----

Print the minimum number of USB flash drives to write Sean's file, if he can split the file between drives.


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

Output
2

Input
3
6
2
3
2

Output
3

Input
2
5
5
10

Output
1



-----Note-----

In the first example Sean needs only two USB flash drives — the first and the third.

In the second example Sean needs all three USB flash drives.

In the third example Sean needs only one USB flash drive and he can use any available USB flash drive — the first or the second.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n cities in Treeland connected with n - 1 bidirectional roads in such that a way that any city is reachable from any other; in other words, the graph of cities and roads is a tree. Treeland is preparing for a seasonal virus epidemic, and currently, they are trying to evaluate different infection scenarios.

In each scenario, several cities are initially infected with different virus species. Suppose that there are k_i virus species in the i-th scenario. Let us denote v_j the initial city for the virus j, and s_j the propagation speed of the virus j. The spread of the viruses happens in turns: first virus 1 spreads, followed by virus 2, and so on. After virus k_i spreads, the process starts again from virus 1.

A spread turn of virus j proceeds as follows. For each city x not infected with any virus at the start of the turn, at the end of the turn it becomes infected with virus j if and only if there is such a city y that:

  * city y was infected with virus j at the start of the turn;
  * the path between cities x and y contains at most s_j edges;
  * all cities on the path between cities x and y (excluding y) were uninfected with any virus at the start of the turn.



Once a city is infected with a virus, it stays infected indefinitely and can not be infected with any other virus. The spread stops once all cities are infected.

You need to process q independent scenarios. Each scenario is described by k_i virus species and m_i important cities. For each important city determine which the virus it will be infected by in the end.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of cities in Treeland.

The following n - 1 lines describe the roads. The i-th of these lines contains two integers x_i and y_i (1 ≤ x_i, y_i ≤ n) — indices of cities connecting by the i-th road. It is guaranteed that the given graph of cities and roads is a tree.

The next line contains a single integer q (1 ≤ q ≤ 2 ⋅ 10^5) — the number of infection scenarios. q scenario descriptions follow.

The description of the i-th scenario starts with a line containing two integers k_i and m_i (1 ≤ k_i, m_i ≤ n) — the number of virus species and the number of important cities in this scenario respectively. It is guaranteed that ∑_{i = 1}^ q k_i and ∑_{i = 1}^ q m_i do not exceed 2 ⋅ 10^5.

The following k_i lines describe the virus species. The j-th of these lines contains two integers v_j and s_j (1 ≤ v_j ≤ n, 1 ≤ s_j ≤ 10^6) – the initial city and the propagation speed of the virus species j. It is guaranteed that the initial cities of all virus species within a scenario are distinct.

The following line contains m_i distinct integers u_1, …, u_{m_i} (1 ≤ u_j ≤ n) — indices of important cities.

Output

Print q lines. The i-th line should contain m_i integers — indices of virus species that cities u_1, …, u_{m_i} are infected with at the end of the i-th scenario.

Example

Input


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


Output


1 2
1 1
1 1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have an integer $n$. Let's define following tree generation as McDic's generation:  Make a complete and full binary tree of $2^{n} - 1$ vertices. Complete and full binary tree means a tree that exactly one vertex is a root, all leaves have the same depth (distance from the root), and all non-leaf nodes have exactly two child nodes.  Select a non-root vertex $v$ from that binary tree.  Remove $v$ from tree and make new edges between $v$'s parent and $v$'s direct children. If $v$ has no children, then no new edges will be made. 

You have a tree. Determine if this tree can be made by McDic's generation. If yes, then find the parent vertex of removed vertex in tree.


-----Input-----

The first line contains integer $n$ ($2 \le n \le 17$).

The $i$-th of the next $2^{n} - 3$ lines contains two integers $a_{i}$ and $b_{i}$ ($1 \le a_{i} \lt b_{i} \le 2^{n} - 2$) — meaning there is an edge between $a_{i}$ and $b_{i}$. It is guaranteed that the given edges form a tree.


-----Output-----

Print two lines.

In the first line, print a single integer — the number of answers. If given tree cannot be made by McDic's generation, then print $0$.

In the second line, print all possible answers in ascending order, separated by spaces. If the given tree cannot be made by McDic's generation, then don't print anything.


-----Examples-----
Input
4
1 2
1 3
2 4
2 5
3 6
3 13
3 14
4 7
4 8
5 9
5 10
6 11
6 12

Output
1
3

Input
2
1 2

Output
2
1 2

Input
3
1 2
2 3
3 4
4 5
5 6

Output
0



-----Note-----

In the first example, $3$ is the only possible answer. $8$ 

In the second example, there are $2$ possible answers. [Image] 

In the third example, the tree can't be generated by McDic's generation.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string s consisting of |s| small english letters.

In one move you can replace any character of this string to the next character in alphabetical order (a will be replaced with b, s will be replaced with t, etc.). You cannot replace letter z with any other letter.

Your target is to make some number of moves (not necessary minimal) to get string abcdefghijklmnopqrstuvwxyz (english alphabet) as a subsequence. Subsequence of the string is the string that is obtained by deleting characters at some positions. You need to print the string that will be obtained from the given string and will be contain english alphabet as a subsequence or say that it is impossible.


-----Input-----

The only one line of the input consisting of the string s consisting of |s| (1 ≤ |s| ≤ 10^5) small english letters.


-----Output-----

If you can get a string that can be obtained from the given string and will contain english alphabet as a subsequence, print it. Otherwise print «-1» (without quotes).


-----Examples-----
Input
aacceeggiikkmmooqqssuuwwyy

Output
abcdefghijklmnopqrstuvwxyz

Input
thereisnoanswer

Output
-1

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