vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
This problem is split into two tasks. In this task, you are required to find the minimum possible answer. In the task Village (Maximum) you are required to find the maximum possible answer. Each task is worth 50 points.

There are N houses in a certain village. A single villager lives in each of the houses. The houses are connected by roads. Each road connects two houses and is exactly 1 kilometer long. From each house it is possible to reach any other using one or several consecutive roads. In total there are N-1 roads in the village.

One day all villagers decided to move to different houses — that is, after moving each house should again have a single villager living in it, but no villager should be living in the same house as before. We would like to know the smallest possible total length in kilometers of the shortest paths between the old and the new houses for all villagers.

<image>

Example village with seven houses 

For example, if there are seven houses connected by roads as shown on the figure, the smallest total length is 8 km (this can be achieved by moving 1 → 6, 2 → 4, 3 → 1, 4 → 2, 5 → 7, 6 → 3, 7 → 5).

Write a program that finds the smallest total length of the shortest paths in kilometers and an example assignment of the new houses to the villagers.

Input

The first line contains an integer N (1 < N ≤ 10^5). Houses are numbered by consecutive integers 1, 2, …, N.

Then N-1 lines follow that describe the roads. Each line contains two integers a and b (1 ≤ a, b ≤ N, a ≠ b) denoting that there is a road connecting houses a and b.

Output

In the first line output the smallest total length of the shortest paths in kilometers.

In the second line describe one valid assignment of the new houses with the smallest total length: N space-separated distinct integers v_1, v_2, …, v_N. For each i, v_i is the house number where the villager from the house i should move (v_i ≠ i). If there are several valid assignments, output any of those.

Scoring

Subtasks: 

  1. (6 points) N ≤ 10 
  2. (19 points) N ≤ 1 000 
  3. (25 points) No further constraints 

Examples

Input


4
1 2
2 3
3 4


Output


4
2 1 4 3


Input


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


Output


8
3 4 6 2 7 1 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has a sequence A of 2 \cdot N integers containing all natural numbers from 1 to N exactly twice.

Let a sequence B containing K elements be a [subsequence] of A. We define a strictly increasing *index* sequence I(B) = [I_{1}, I_{2}, \ldots, I_{K}] such that, B can be written as [A_{I_{1}}, A_{I_{2}}, \ldots, A_{I_{K}}].
 
A pair of subsequences (P,Q) is said to be *good* if all of the following conditions satisfy:
Both subsequences have the same length. In other words, |P| = |Q|, where |P| and |Q| denote the lengths of P and Q respectively; 
The subsequences P and Q are disjoint. In other words, there are no common elements between I(P) and I(Q);
The subsequences are equal. In other words, P_{j} = Q_{j} for all (1≤ j ≤ |P|).

Find the total number of distinct ordered pairs of subsequences (P,Q) that are *good*.  
Two ordered pairs (P_{1}, Q_{1}) and (P_{2}, Q_{2}) are considered different iff I(P_{1}) \ne I(P_{2}) or I(Q_{1}) \ne I(Q_{2}).

Since the answer can be very large, print it modulo 998244353.

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

- First line contains T − the number of test cases. The description of the test cases is as follows.
- The first line of each test case contains a single integer N − the value of N.
- The second line of each test case contains 2 \cdot N integers A_{1}, A_{2}, \ldots, A_{2 \cdot N}​. 

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

For each test case, output a single integer − the total number of distinct ordered pairs of subsequences (P,Q) that are *good* modulo 998244353.

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

$1 ≤ T ≤ 2\cdot 10^{5}$
$1 ≤ N ≤ 2\cdot 10^{5}$
$1 ≤ A_{i} ≤ N$
- Sum of $N$ over all test cases does not exceed $6\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
1
1 1
2
1 1 2 2
2
1 2 1 2
----- Sample Output 1 ------ 
2
8
6
----- explanation 1 ------ 
Test case $1$: Possible ordered pairs are: $([A_{1}], [A_{2}])$, $([A_{2}], [A_{1}])$.

Test case $2$: Possible ordered pairs are: $([A_{1}],[A_{2}])$, $([A_{2}], [A_{1}])$, $([A_{3}], [A_{4}])$,  $([A_{4}], [A_{3}])$, $([A_{1}, A_{3}], [A_{2}, A_{4}])$, $([A_{2}, A_{4}], [A_{1}, A_{3}])$, $([A_{1}, A_{4}], [A_{2}, A_{3}])$, $([A_{2}, A_{3}], [A_{1}, A_{4}])$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ivar the Boneless is a great leader. He is trying to capture Kattegat from Lagertha. The war has begun and wave after wave Ivar's warriors are falling in battle.

Ivar has $n$ warriors, he places them on a straight line in front of the main gate, in a way that the $i$-th warrior stands right after $(i-1)$-th warrior. The first warrior leads the attack.

Each attacker can take up to $a_i$ arrows before he falls to the ground, where $a_i$ is the $i$-th warrior's strength.

Lagertha orders her warriors to shoot $k_i$ arrows during the $i$-th minute, the arrows one by one hit the first still standing warrior. After all Ivar's warriors fall and all the currently flying arrows fly by, Thor smashes his hammer and all Ivar's warriors get their previous strengths back and stand up to fight again. In other words, if all warriors die in minute $t$, they will all be standing to fight at the end of minute $t$.

The battle will last for $q$ minutes, after each minute you should tell Ivar what is the number of his standing warriors.

Input Specification:
The first line contains two integers $n$ and $q$ ($1 \le n, q \leq 200\,000$) — the number of warriors and the number of minutes in the battle.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) that represent the warriors' strengths.

The third line contains $q$ integers $k_1, k_2, \ldots, k_q$ ($1 \leq k_i \leq 10^{14}$), the $i$-th of them represents Lagertha's order at the $i$-th minute: $k_i$ arrows will attack the warriors.

Output Specification:
Output $q$ lines, the $i$-th of them is the number of standing warriors after the $i$-th minute.

Demo Input:
['5 5\n1 2 1 2 1\n3 10 1 1 1\n', '4 4\n1 2 3 4\n9 1 10 6\n']

Demo Output:
['3\n5\n4\n4\n3\n', '1\n4\n4\n1\n']

Note:
In the first example: 
 -  after the 1-st minute, the 1-st and 2-nd warriors die. -  after the 2-nd minute all warriors die (and all arrows left over are wasted), then they will be revived thus answer is 5 — all warriors are alive. -  after the 3-rd minute, the 1-st warrior dies. -  after the 4-th minute, the 2-nd warrior takes a hit and his strength decreases by 1. -  after the 5-th minute, the 2-nd warrior dies.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Soroush and Keshi each have a labeled and rooted tree on n vertices. Both of their trees are rooted from vertex 1.

Soroush and Keshi used to be at war. After endless decades of fighting, they finally became allies to prepare a Codeforces round. To celebrate this fortunate event, they decided to make a memorial graph on n vertices.

They add an edge between vertices u and v in the memorial graph if both of the following conditions hold: 

  * One of u or v is the ancestor of the other in Soroush's tree. 
  * Neither of u or v is the ancestor of the other in Keshi's tree. 



Here vertex u is considered ancestor of vertex v, if u lies on the path from 1 (the root) to the v.

Popping out of nowhere, Mashtali tried to find the maximum clique in the memorial graph for no reason. He failed because the graph was too big. 

Help Mashtali by finding the size of the maximum clique in the memorial graph.

As a reminder, clique is a subset of vertices of the graph, each two of which are connected by an edge.

Input

The first line contains an integer t (1≤ t≤ 3 ⋅ 10^5) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer n (2≤ n≤ 3 ⋅ 10^5).

The second line of each test case contains n-1 integers a_2, …, a_n (1 ≤ a_i < i), a_i being the parent of the vertex i in Soroush's tree.

The third line of each test case contains n-1 integers b_2, …, b_n (1 ≤ b_i < i), b_i being the parent of the vertex i in Keshi's tree.

It is guaranteed that the given graphs are trees.

It is guaranteed that the sum of n over all test cases doesn't exceed 3 ⋅ 10^5.

Output

For each test case print a single integer — the size of the maximum clique in the memorial graph.

Example

Input


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


Output


1
4
1
3

Note

In the first and third test cases, you can pick any vertex.

In the second test case, one of the maximum cliques is \{2, 3, 4, 5\}.

In the fourth test case, one of the maximum cliques is \{3, 4, 6\}.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
A little boy Gerald entered a clothes shop and found out something very unpleasant: not all clothes turns out to match. For example, Gerald noticed that he looks rather ridiculous in a smoking suit and a baseball cap.

Overall the shop sells *n* clothing items, and exactly *m* pairs of clothing items match. Each item has its price, represented by an integer number of rubles. Gerald wants to buy three clothing items so that they matched each other. Besides, he wants to spend as little money as possible. Find the least possible sum he can spend.

Input Specification:
The first input file line contains integers *n* and *m* — the total number of clothing items in the shop and the total number of matching pairs of clothing items ().

Next line contains *n* integers *a**i* (1<=≤<=*a**i*<=≤<=106) — the prices of the clothing items in rubles.

Next *m* lines each contain a pair of space-separated integers *u**i* and *v**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*,<=*u**i*<=≠<=*v**i*). Each such pair of numbers means that the *u**i*-th and the *v**i*-th clothing items match each other. It is guaranteed that in each pair *u**i* and *v**i* are distinct and all the unordered pairs (*u**i*,<=*v**i*) are different.

Output Specification:
Print the only number — the least possible sum in rubles that Gerald will have to pay in the shop. If the shop has no three clothing items that would match each other, print "-1" (without the quotes).

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

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

Note:
In the first test there only are three pieces of clothing and they all match each other. Thus, there is only one way — to buy the 3 pieces of clothing; in this case he spends 6 roubles.

The second test only has three pieces of clothing as well, yet Gerald can't buy them because the first piece of clothing does not match the third one. Thus, there are no three matching pieces of clothing. The answer is -1.

In the third example there are 4 pieces of clothing, but Gerald can't buy any 3 of them simultaneously. The answer is -1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pavel is going to make a game of his dream. However, he knows that he can't make it on his own so he founded a development company and hired n workers of staff. Now he wants to pick n workers from the staff who will be directly responsible for developing a game.

Each worker has a certain skill level vi. Besides, each worker doesn't want to work with the one whose skill is very different. In other words, the i-th worker won't work with those whose skill is less than li, and with those whose skill is more than ri.

Pavel understands that the game of his dream isn't too hard to develop, so the worker with any skill will be equally useful. That's why he wants to pick a team of the maximum possible size. Help him pick such team.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of workers Pavel hired.

Each of the following n lines contains three space-separated integers li, vi, ri (1 ≤ li ≤ vi ≤ ri ≤ 3·105) — the minimum skill value of the workers that the i-th worker can work with, the i-th worker's skill and the maximum skill value of the workers that the i-th worker can work with.

Output

In the first line print a single integer m — the number of workers Pavel must pick for developing the game.

In the next line print m space-separated integers — the numbers of the workers in any order.

If there are multiple optimal solutions, print any of them.

Examples

Input

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


Output

3
1 3 4


Input

6
3 5 16
1 6 11
4 8 12
7 9 16
2 10 14
8 13 15


Output

4
1 2 3 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the following process. You have a binary string (a string where each character is either 0 or 1) $w$ of length $n$ and an integer $x$. You build a new binary string $s$ consisting of $n$ characters. The $i$-th character of $s$ is chosen as follows:

  if the character $w_{i-x}$ exists and is equal to 1, then $s_i$ is 1 (formally, if $i > x$ and $w_{i-x} = $ 1, then $s_i = $ 1);  if the character $w_{i+x}$ exists and is equal to 1, then $s_i$ is 1 (formally, if $i + x \le n$ and $w_{i+x} = $ 1, then $s_i = $ 1);  if both of the aforementioned conditions are false, then $s_i$ is 0. 

You are given the integer $x$ and the resulting string $s$. Reconstruct the original string $w$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Each test case consists of two lines. The first line contains the resulting string $s$ ($2 \le |s| \le 10^5$, each character of $s$ is either 0 or 1). The second line contains one integer $x$ ($1 \le x \le |s| - 1$).

The total length of all strings $s$ in the input does not exceed $10^5$.


-----Output-----

For each test case, print the answer on a separate line as follows:

  if no string $w$ can produce the string $s$ at the end of the process, print $-1$;  otherwise, print the binary string $w$ consisting of $|s|$ characters. If there are multiple answers, print any of them. 


-----Example-----
Input
3
101110
2
01
1
110
1

Output
111011
10
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The number ```89``` is the first positive integer that has a particular, curious property:

The square of ```89``` is ```7921```; ```89² = 7921```

The reverse of ```7921``` is ```1297```, and ```1297``` is a prime number.

The cube of ```89``` is ```704969```; ```89³ = 704969```

The reverse of ```704969``` is ```969407```, and ```969407``` is a prime number.

The first four terms of this sequence having this special property are:
```
n-th term      term value
    1               89 
    2              271
    3              325
    4              328
```

Create a function ```sq_cub_rev_prime()```, that receives the ordinal number of the sequence and outputs its correspoding value.

Use the above table to show how the function should work:
```python 
sq_cub_rev_prime(1) == 89 
sq_cub_rev_prime(2) == 271
sq_cub_rev_prime(3) == 325
sq_cub_rev_prime(4) == 328
```
Your code will be tested up to the 250th term

This is not a registered sequence of OESIS, so if you are one of the first ten people that solve this kata, you may have the privilege to register the sequence at https://oeis.org, with your name. If you do so, please, mention in your biography that you are a Codewarrior.

Memoize your results to pass the tests.

Enjoy it!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: MUH and Cube Walls

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polar bears Menshykov and Uslada from the zoo of St. Petersburg and elephant Horace from the zoo of Kiev got hold of lots of wooden cubes somewhere. They started making cube towers by placing the cubes one on top of the other. They defined multiple towers standing in a line as a wall. A wall can consist of towers of different heights.

Horace was the first to finish making his wall. He called his wall an elephant. The wall consists of *w* towers. The bears also finished making their wall but they didn't give it a name. Their wall consists of *n* towers. Horace looked at the bears' tower and wondered: in how many parts of the wall can he "see an elephant"? He can "see an elephant" on a segment of *w* contiguous towers if the heights of the towers on the segment match as a sequence the heights of the towers in Horace's wall. In order to see as many elephants as possible, Horace can raise and lower his wall. He even can lower the wall below the ground level (see the pictures to the samples for clarification).

Your task is to count the number of segments where Horace can "see an elephant".

Input Specification:
The first line contains two integers *n* and *w* (1<=≤<=*n*,<=*w*<=≤<=2·105) — the number of towers in the bears' and the elephant's walls correspondingly. The second line contains *n* integers *a**i* (1<=≤<=*a**i*<=≤<=109) — the heights of the towers in the bears' wall. The third line contains *w* integers *b**i* (1<=≤<=*b**i*<=≤<=109) — the heights of the towers in the elephant's wall.

Output Specification:
Print the number of segments in the bears' wall where Horace can "see an elephant".

Demo Input:
['13 5\n2 4 5 5 4 3 2 2 2 3 3 2 1\n3 4 4 3 2\n']

Demo Output:
['2']

Note:
The picture to the left shows Horace's wall from the sample, the picture to the right shows the bears' wall. The segments where Horace can "see an elephant" are in gray.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the beginning of the new year Keivan decided to reverse his name. He doesn't like palindromes, so he changed Naviek to Navick.

He is too selfish, so for a given n he wants to obtain a string of n characters, each of which is either 'a', 'b' or 'c', with no palindromes of length 3 appearing in the string as a substring. For example, the strings "abc" and "abca" suit him, while the string "aba" doesn't. He also want the number of letters 'c' in his string to be as little as possible.


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 2·10^5) — the length of the string.


-----Output-----

Print the string that satisfies all the constraints.

If there are multiple answers, print any of them.


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

Output
aa

Input
3

Output
bba



-----Note-----

A palindrome is a sequence of characters which reads the same backward and forward.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pupils decided to go to amusement park. Some of them were with parents. In total, n people came to the park and they all want to get to the most extreme attraction and roll on it exactly once.

Tickets for group of x people are sold on the attraction, there should be at least one adult in each group (it is possible that the group consists of one adult). The ticket price for such group is c_1 + c_2·(x - 1)^2 (in particular, if the group consists of one person, then the price is c_1). 

All pupils who came to the park and their parents decided to split into groups in such a way that each visitor join exactly one group, and the total price of visiting the most extreme attraction is as low as possible. You are to determine this minimum possible total price. There should be at least one adult in each group. 


-----Input-----

The first line contains three integers n, c_1 and c_2 (1 ≤ n ≤ 200 000, 1 ≤ c_1, c_2 ≤ 10^7) — the number of visitors and parameters for determining the ticket prices for a group.

The second line contains the string of length n, which consists of zeros and ones. If the i-th symbol of the string is zero, then the i-th visitor is a pupil, otherwise the i-th person is an adult. It is guaranteed that there is at least one adult. It is possible that there are no pupils.


-----Output-----

Print the minimum price of visiting the most extreme attraction for all pupils and their parents. Each of them should roll on the attraction exactly once.


-----Examples-----
Input
3 4 1
011

Output
8

Input
4 7 2
1101

Output
18



-----Note-----

In the first test one group of three people should go to the attraction. Then they have to pay 4 + 1 * (3 - 1)^2 = 8.

In the second test it is better to go to the attraction in two groups. The first group should consist of two adults (for example, the first and the second person), the second should consist of one pupil and one adult (the third and the fourth person). Then each group will have a size of two and for each the price of ticket is 7 + 2 * (2 - 1)^2 = 9. Thus, the total price for two groups is 18.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya is currently at a car rental service, and he wants to reach cinema. The film he has bought a ticket for starts in *t* minutes. There is a straight road of length *s* from the service to the cinema. Let's introduce a coordinate system so that the car rental service is at the point 0, and the cinema is at the point *s*.

There are *k* gas stations along the road, and at each of them you can fill a car with any amount of fuel for free! Consider that this operation doesn't take any time, i.e. is carried out instantly.

There are *n* cars in the rental service, *i*-th of them is characterized with two integers *c**i* and *v**i* — the price of this car rent and the capacity of its fuel tank in liters. It's not allowed to fuel a car with more fuel than its tank capacity *v**i*. All cars are completely fueled at the car rental service.

Each of the cars can be driven in one of two speed modes: normal or accelerated. In the normal mode a car covers 1 kilometer in 2 minutes, and consumes 1 liter of fuel. In the accelerated mode a car covers 1 kilometer in 1 minutes, but consumes 2 liters of fuel. The driving mode can be changed at any moment and any number of times.

Your task is to choose a car with minimum price such that Vasya can reach the cinema before the show starts, i.e. not later than in *t* minutes. Assume that all cars are completely fueled initially.

Input Specification:
The first line contains four positive integers *n*, *k*, *s* and *t* (1<=≤<=*n*<=≤<=2·105, 1<=≤<=*k*<=≤<=2·105, 2<=≤<=*s*<=≤<=109, 1<=≤<=*t*<=≤<=2·109) — the number of cars at the car rental service, the number of gas stations along the road, the length of the road and the time in which the film starts. 

Each of the next *n* lines contains two positive integers *c**i* and *v**i* (1<=≤<=*c**i*,<=*v**i*<=≤<=109) — the price of the *i*-th car and its fuel tank capacity.

The next line contains *k* distinct integers *g*1,<=*g*2,<=...,<=*g**k* (1<=≤<=*g**i*<=≤<=*s*<=-<=1) — the positions of the gas stations on the road in arbitrary order.

Output Specification:
Print the minimum rent price of an appropriate car, i.e. such car that Vasya will be able to reach the cinema before the film starts (not later than in *t* minutes). If there is no appropriate car, print -1.

Demo Input:
['3 1 8 10\n10 8\n5 7\n11 9\n3\n', '2 2 10 18\n10 4\n20 6\n5 3\n']

Demo Output:
['10\n', '20\n']

Note:
In the first sample, Vasya can reach the cinema in time using the first or the third cars, but it would be cheaper to choose the first one. Its price is equal to 10, and the capacity of its fuel tank is 8. Then Vasya can drive to the first gas station in the accelerated mode in 3 minutes, spending 6 liters of fuel. After that he can full the tank and cover 2 kilometers in the normal mode in 4 minutes, spending 2 liters of fuel. Finally, he drives in the accelerated mode covering the remaining 3 kilometers in 3 minutes and spending 6 liters of fuel.

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