apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
The only difference between easy and hard versions is constraints.

There are $$$n$$$ kids, each of them is reading a unique book. At the end of any day, the $$$i$$$-th kid will give his book to the $$$p_i$$$-th kid (in case of $$$i = p_i$$$ the kid will give his book to himself). It is guaranteed that all values of $$$p_i$$$ are distinct integers from $$$1$$$ to $$$n$$$ (i.e. $$$p$$$ is a permutation). The sequence $$$p$$$ doesn't change from day to day, it is fixed.

For example, if $$$n=6$$$ and $$$p=[4, 6, 1, 3, 5, 2]$$$ then at the end of the first day the book of the $$$1$$$-st kid will belong to the $$$4$$$-th kid, the $$$2$$$-nd kid will belong to the $$$6$$$-th kid and so on. At the end of the second day the book of the $$$1$$$-st kid will belong to the $$$3$$$-th kid, the $$$2$$$-nd kid will belong to the $$$2$$$-th kid and so on.

Your task is to determine the number of the day the book of the $$$i$$$-th child is returned back to him for the first time for every $$$i$$$ from $$$1$$$ to $$$n$$$.

Consider the following example: $$$p = [5, 1, 2, 4, 3]$$$. The book of the $$$1$$$-st kid will be passed to the following kids:

- after the $$$1$$$-st day it will belong to the $$$5$$$-th kid,
- after the $$$2$$$-nd day it will belong to the $$$3$$$-rd kid,
- after the $$$3$$$-rd day it will belong to the $$$2$$$-nd kid,
- after the $$$4$$$-th day it will belong to the $$$1$$$-st kid.

So after the fourth day, the book of the first kid will return to its owner. The book of the fourth kid will return to him for the first time after exactly one day.

You have to answer $$$q$$$ independent queries.

## Input Format
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 200$$$) — the number of queries. Then $$$q$$$ queries follow.

The first line of the query contains one integer $$$n$$$ ($$$1 \le n \le 200$$$) — the number of kids in the query. The second line of the query contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are distinct, i.e. $$$p$$$ is a permutation), where $$$p_i$$$ is the kid which will get the book of the $$$i$$$-th kid.

## Output Format
For each query, print the answer on it: $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ is the number of the day the book of the $$$i$$$-th child is returned back to him for the first time in this query.

## Examples
```input
6
5
1 2 3 4 5
3
2 3 1
6
4 6 2 1 5 3
1
1
4
3 4 1 2
5
5 1 2 4 3
```
```output
1 1 1 1 1 
3 3 3 
2 3 3 2 1 3 
1 
2 2 2 2 
4 4 4 1 4
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
The only difference between easy and hard versions is the maximum value of $$$n$$$.

You are given a positive integer number $$$n$$$. You really love good numbers so you want to find the smallest good number greater than or equal to $$$n$$$.

The positive integer is called good if it can be represented as a sum of distinct powers of $$$3$$$ (i.e. no duplicates of powers of $$$3$$$ are allowed).

For example:

- $$$30$$$ is a good number: $$$30 = 3^3 + 3^1$$$,
- $$$1$$$ is a good number: $$$1 = 3^0$$$,
- $$$12$$$ is a good number: $$$12 = 3^2 + 3^1$$$,
- but $$$2$$$ is not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ ($$$2 = 3^0 + 3^0$$$),
- $$$19$$$ is not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ (for example, the representations $$$19 = 3^2 + 3^2 + 3^0 = 3^2 + 3^1 + 3^1 + 3^1 + 3^0$$$ are invalid),
- $$$20$$$ is also not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ (for example, the representation $$$20 = 3^2 + 3^2 + 3^0 + 3^0$$$ is invalid).

Note, that there exist other representations of $$$19$$$ and $$$20$$$ as sums of powers of $$$3$$$ but none of them consists of distinct powers of $$$3$$$.

For the given positive integer $$$n$$$ find such smallest $$$m$$$ ($$$n \le m$$$) that $$$m$$$ is a good number.

You have to answer $$$q$$$ independent queries.

## Input Format
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 500$$$) — the number of queries. Then $$$q$$$ queries follow.

The only line of the query contains one integer $$$n$$$ ($$$1 \le n \le 10^4$$$).

## Output Format
For each query, print such smallest integer $$$m$$$ (where $$$n \le m$$$) that $$$m$$$ is a good number.

## Examples
```input
7
1
2
6
13
14
3620
10000
```
```output
1
3
9
13
27
6561
19683
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
The only difference between easy and hard versions is the maximum value of $$$n$$$.

You are given a positive integer number $$$n$$$. You really love good numbers so you want to find the smallest good number greater than or equal to $$$n$$$.

The positive integer is called good if it can be represented as a sum of distinct powers of $$$3$$$ (i.e. no duplicates of powers of $$$3$$$ are allowed).

For example:

- $$$30$$$ is a good number: $$$30 = 3^3 + 3^1$$$,
- $$$1$$$ is a good number: $$$1 = 3^0$$$,
- $$$12$$$ is a good number: $$$12 = 3^2 + 3^1$$$,
- but $$$2$$$ is not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ ($$$2 = 3^0 + 3^0$$$),
- $$$19$$$ is not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ (for example, the representations $$$19 = 3^2 + 3^2 + 3^0 = 3^2 + 3^1 + 3^1 + 3^1 + 3^0$$$ are invalid),
- $$$20$$$ is also not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ (for example, the representation $$$20 = 3^2 + 3^2 + 3^0 + 3^0$$$ is invalid).

Note, that there exist other representations of $$$19$$$ and $$$20$$$ as sums of powers of $$$3$$$ but none of them consists of distinct powers of $$$3$$$.

For the given positive integer $$$n$$$ find such smallest $$$m$$$ ($$$n \le m$$$) that $$$m$$$ is a good number.

You have to answer $$$q$$$ independent queries.

## Input Format
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 500$$$) — the number of queries. Then $$$q$$$ queries follow.

The only line of the query contains one integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$).

## Output Format
For each query, print such smallest integer $$$m$$$ (where $$$n \le m$$$) that $$$m$$$ is a good number.

## Examples
```input
8
1
2
6
13
14
3620
10000
1000000000000000000
```
```output
1
3
9
13
27
6561
19683
1350851717672992089
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
The only difference between easy and hard versions is constraints.

You are given $$$n$$$ segments on the coordinate axis $$$OX$$$. Segments can intersect, lie inside each other and even coincide. The $$$i$$$-th segment is $$$[l_i; r_i]$$$ ($$$l_i \le r_i$$$) and it covers all integer points $$$j$$$ such that $$$l_i \le j \le r_i$$$.

The integer point is called bad if it is covered by strictly more than $$$k$$$ segments.

Your task is to remove the minimum number of segments so that there are no bad points at all.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the number of segments and the maximum number of segments by which each integer point can be covered.

The next $$$n$$$ lines contain segments. The $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$) — the endpoints of the $$$i$$$-th segment.

## Output Format
In the first line print one integer $$$m$$$ ($$$0 \le m \le n$$$) — the minimum number of segments you need to remove so that there are no bad points.

In the second line print $$$m$$$ distinct integers $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i \le n$$$) — indices of segments you remove in any order. If there are multiple answers, you can print any of them.

## Examples
```input
7 2
11 11
9 11
7 8
8 9
7 8
9 11
7 9
```
```output
3
4 6 7
```
-----
```input
5 1
29 30
30 30
29 29
28 30
30 30
```
```output
3
1 4 5
```
-----
```input
6 1
2 3
3 3
2 3
2 2
2 3
2 3
```
```output
4
1 3 5 6
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a tree, which consists of $$$n$$$ vertices. Recall that a tree is a connected undirected graph without cycles.

Example of a tree.

Vertices are numbered from $$$1$$$ to $$$n$$$. All vertices have weights, the weight of the vertex $$$v$$$ is $$$a_v$$$.

Recall that the distance between two vertices in the tree is the number of edges on a simple path between them.

Your task is to find the subset of vertices with the maximum total weight (the weight of the subset is the sum of weights of all vertices in it) such that there is no pair of vertices with the distance $$$k$$$ or less between them in this subset.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 200$$$) — the number of vertices in the tree and the distance restriction, respectively.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$), where $$$a_i$$$ is the weight of the vertex $$$i$$$.

The next $$$n - 1$$$ lines contain edges of the tree. Edge $$$i$$$ is denoted by two integers $$$u_i$$$ and $$$v_i$$$ — the labels of vertices it connects ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$).

It is guaranteed that the given edges form a tree.

## Output Format
Print one integer — the maximum total weight of the subset in which all pairs of vertices have distance more than $$$k$$$.

## Examples
```input
5 1
1 2 3 4 5
1 2
2 3
3 4
3 5
```
```output
11
```
-----
```input
7 2
2 1 2 1 2 1 1
6 4
1 5
3 1
2 3
7 5
7 4
```
```output
4
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Lengths are measures in Baden in inches and feet. To a length from centimeters it is enough to know that an inch equals three centimeters in Baden and one foot contains 12 inches.

You are given a length equal to n centimeters. Your task is to convert it to feet and inches so that the number of feet was maximum. The result should be an integer rounded to the closest value containing an integral number of inches.

Note that when you round up, 1 cm rounds up to 0 inches and 2 cm round up to 1 inch.

## Input Format
The only line contains an integer n (1 ≤ n ≤ 10000).

## Output Format
Print two non-negative space-separated integers a and b, where a is the numbers of feet and b is the number of inches.

## Examples
```input
42
```
```output
1 2
```
-----
```input
5
```
```output
0 2
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let's define a string <x> as an opening tag, where x is any small letter of the Latin alphabet. Each opening tag matches a closing tag of the type </x>, where x is the same letter.

Tegs can be nested into each other: in this case one opening and closing tag pair is located inside another pair.

Let's define the notion of a XML-text:

- an empty string is a XML-text
- if s is a XML-text, then s'=<a>+s+</a> also is a XML-text, where a is any small Latin letter
- if s1, s2 are XML-texts, then s1+s2 also is a XML-text

You are given a XML-text (it is guaranteed that the text is valid), your task is to print in the following form:

- each tag (opening and closing) is located on a single line
- print before the tag 2 * h spaces, where h is the level of the tag's nestedness.

## Input Format
The input data consists on the only non-empty string — the XML-text, its length does not exceed 1000 characters. It is guaranteed that the text is valid. The text contains no spaces.

## Output Format
Print the given XML-text according to the above-given rules.

## Examples
```input
<a><b><c></c></b></a>
```
```output
<a>
<b>
<c>
</c>
</b>
</a>
```
-----
```input
<a><b></b><d><c></c></d></a>
```
```output
<a>
<b>
</b>
<d>
<c>
</c>
</d>
</a>
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Everyone knows that hobbits love to organize all sorts of parties and celebrations. There are n hobbits living in the Shire. They decided to organize the Greatest Party (GP) that would last for several days. Next day the hobbits wrote a guest list, some non-empty set containing all the inhabitants of the Shire. To ensure that everybody enjoy themselves and nobody gets bored, for any two days (say, days A and B) of the GP there existed at least one hobbit, invited to come on day A and on day B. However, to ensure that nobody has a row, for any three different days A, B, C there shouldn't be a hobbit invited on days A, B and C. The Shire inhabitants are keen on keeping the GP going for as long as possible. Your task is given number n, to indicate the GP's maximum duration and the guest lists for each day.

## Input Format
The first line contains an integer n (3 ≤ n ≤ 10000), representing the number of hobbits.

## Output Format
In the first output line print a number k — the maximum duration of GP in days. Then on k lines print the guest lists, (the guests should be separated by spaces). Print each guest list on the single line. Each list can contain an arbitrary positive number of hobbits. The hobbits are numbered with integers from 1 to n.

## Examples
```input
4
```
```output
3
1 2
1 3
2 3
```
-----
```input
5
```
```output
3
1 2
1 3
2 3
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
An arithmetic progression is such a non-empty sequence of numbers where the difference between any two successive numbers is constant. This constant number is called common difference. For example, the sequence 3, 7, 11, 15 is an arithmetic progression. The definition implies that any sequences whose length equals 1 or 2 are arithmetic and all sequences whose length equals 0 are non-arithmetic.

You are given a sequence of different integers a1, a2, ..., an. You should either split it into two arithmetic progressions or find out that the operation is impossible to perform. Splitting assigns each member of the given sequence to one of two progressions, but the relative order of numbers does not change. Splitting is an inverse operation to merging.

## Input Format
The first line contains a positive integer n (2 ≤ n ≤ 30000), n is the length of the given sequence. The second line contains elements of the given sequence a1, a2, ..., an ( - 108 ≤ ai ≤ 108). The elements of the progression are different integers.

## Output Format
Print the required arithmetic progressions, one per line. The progressions can be positioned in any order. Each progression should contain at least one number. If there's no solution, then print "No solution" (without the quotes)in the only line of the input file. If there are several solutions, print any of them.

## Examples
```input
6
4 1 2 7 3 10
```
```output
1 2 3
4 7 10
```
-----
```input
5
1 2 3 -2 -7
```
```output
1 2 3
-2 -7
```

## Note
In the second sample another solution is also possible (number three can be assigned to the second progression): 1, 2 and 3, -2, -7.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 8.0 seconds
Memory limit: 256.0 MB

# Problem
The MST (Meaningless State Team) company won another tender for an important state reform in Berland.

There are n cities in Berland, some pairs of the cities are connected by roads. Each road has its price. One can move along any road in any direction. The MST team should carry out the repair works on some set of roads such that one can get from any city to any other one moving only along the repaired roads. Moreover, this set should contain exactly k capital roads (that is, the roads that start or finish in the capital). The number of the capital is 1.

As the budget has already been approved, the MST Company will profit by finding the set with minimum lengths of roads.

## Input Format
The first input line contains three integers n, m, k (1 ≤ n ≤ 5000;0 ≤ m ≤ 105;0 ≤ k < 5000), where n is the number of cities in the country, m is the number of roads in the country, k is the number of capital roads in the required set. Then m lines enumerate the roads in question. Each road is specified by three numbers ai, bi, wi (1 ≤ ai, bi ≤ n; 1 ≤ w ≤ 105), where ai, bi are the numbers of cities linked by a road and wi is its length.

Between each pair of cities no more than one road exists. There are no roads that start and finish in one city. The capital's number is 1.

## Output Format
In the first line print the number of roads in the required set. The second line should contain the numbers of roads included in the sought set. If the sought set does not exist, print -1.

## Examples
```input
4 5 2
1 2 1
2 3 1
3 4 1
1 3 3
1 4 2
```
```output
3
1 5 2
```

Now solve the problem and return the code.