vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Edo has got a collection of n refrigerator magnets!

He decided to buy a refrigerator and hang the magnets on the door. The shop can make the refrigerator with any size of the door that meets the following restrictions: the refrigerator door must be rectangle, and both the length and the width of the door must be positive integers.

Edo figured out how he wants to place the magnets on the refrigerator. He introduced a system of coordinates on the plane, where each magnet is represented as a rectangle with sides parallel to the coordinate axes.

Now he wants to remove no more than k magnets (he may choose to keep all of them) and attach all remaining magnets to the refrigerator door, and the area of ​​the door should be as small as possible. A magnet is considered to be attached to the refrigerator door if its center lies on the door or on its boundary. The relative positions of all the remaining magnets must correspond to the plan.

Let us explain the last two sentences. Let's suppose we want to hang two magnets on the refrigerator. If the magnet in the plan has coordinates of the lower left corner (x_1, y_1) and the upper right corner (x_2, y_2), then its center is located at ($\frac{x_{1} + x_{2}}{2}$, $\frac{y_{1} + y_{2}}{2}$) (may not be integers). By saying the relative position should correspond to the plan we mean that the only available operation is translation, i.e. the vector connecting the centers of two magnets in the original plan, must be equal to the vector connecting the centers of these two magnets on the refrigerator.

The sides of the refrigerator door must also be parallel to coordinate axes.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ min(10, n - 1)) — the number of magnets that Edo has and the maximum number of magnets Edo may not place on the refrigerator.

Next n lines describe the initial plan of placing magnets. Each line contains four integers x_1, y_1, x_2, y_2 (1 ≤ x_1 < x_2 ≤ 10^9, 1 ≤ y_1 < y_2 ≤ 10^9) — the coordinates of the lower left and upper right corners of the current magnet. The magnets can partially overlap or even fully coincide.


-----Output-----

Print a single integer — the minimum area of the door of refrigerator, which can be used to place at least n - k magnets, preserving the relative positions. 


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

Output
1

Input
4 1
1 1 2 2
1 9 2 10
9 9 10 10
9 1 10 2

Output
64

Input
3 0
1 1 2 2
1 1 1000000000 1000000000
1 3 8 12

Output
249999999000000001



-----Note-----

In the first test sample it is optimal to remove either the first or the third magnet. If we remove the first magnet, the centers of two others will lie at points (2.5, 2.5) and (3.5, 3.5). Thus, it is enough to buy a fridge with door width 1 and door height 1, the area of the door also equals one, correspondingly.

In the second test sample it doesn't matter which magnet to remove, the answer will not change — we need a fridge with door width 8 and door height 8.

In the third sample you cannot remove anything as k = 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Neelix has been working on making the Altonian warp bubble power itself up. While waiting for the system checks to complete, he saw a number on his screen and wondered if there is a number that powers itself up to this number.

-----Input-----
The first and only input line consists of a single integer $n$, the number Neelix saw on his screen.

-----Output-----
Output the number $x$, where $x^x = n$. Your answer must have an absolute or relative error of at most $10^{-6}$.

-----Limits-----
 - $1 \leq n \leq 10000000000$

-----Examples-----
Sample Input:
4
Sample Output:
2.0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
If we write out the digits of "60" as English words we get "sixzero"; the number of letters in "sixzero" is seven. The number of letters in "seven" is five. The number of letters in "five" is four. The number of letters in "four" is four: we have reached a stable equilibrium.

Note: for integers larger than 9, write out the names of each digit in a single word (instead of the proper name of the number in English). For example, write 12 as "onetwo" (instead of twelve), and 999 as "nineninenine" (instead of nine hundred and ninety-nine).

For any integer between 0 and 999, return an array showing the path from that integer to a stable equilibrium:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Johan has a really boring job at the airport. It is his duty to make sure no bags collide when sliding onto the circular conveyor belt in the luggage pick-up zone. All pieces of luggage are loaded onto a straight conveyer belt which ends above the circular conveyor belt. Johan is then manually varying the speed of the straight conveyor so that no collisions occur. He would rather set a constant speed so that he can go to the fika room. There is a sensor at the start of the long conveyor belt so that he can get the positions of all pieces of luggage into his computer. Now all he needs is a program giving him the maximum speed that will avoid all collisions.

The circular conveyor belt moves at a constant speed of $1$ m/s. If a piece of luggage is dropped on the circular belt within one meter of the position of another piece of luggage they may collide, so this should be avoided. Some bags might be picked up on the first round, but you can not know in advance which will be left. The straight conveyor can be set to any speed between $0.1$ m/s and $10$ m/s.

-----Input-----
The first line of input contains two positive integers $N$ and $L$ ($1 \leq N \leq L \leq 1000$), where $N$ is the number of pieces of luggage and $L$ is the length of the circular conveyor belt in meters. The second line contains $N$ unique space-separated numbers $x_ i$ ($0 \leq x_ i \leq 1000$) with two digits after the decimal point, denoting luggage positions in meters.

-----Output-----
Output the maximum speed $v$ in m/s ($0.1 \leq v \leq 10$) that makes sure no collisions will occur, or “no fika” if there is no such speed. The answer is considered correct if it has an absolute error of at most $10^{-9}$.

You may assume that when an optimal $v$ exists, each speed in the interval $[v - 10^{-9}, v]$ will also be a valid speed.

-----Examples-----
Sample Input:
2 3
0.00 2.00
Sample Output:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A k-multiple free set is a set of integers where there is no pair of integers where one is equal to another integer multiplied by k. That is, there are no two integers x and y (x < y) from the set, such that y = x·k.

You're given a set of n distinct positive integers. Your task is to find the size of it's largest k-multiple free subset.


-----Input-----

The first line of the input contains two integers n and k (1 ≤ n ≤ 10^5, 1 ≤ k ≤ 10^9). The next line contains a list of n distinct positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).

All the numbers in the lines are separated by single spaces.


-----Output-----

On the only line of the output print the size of the largest k-multiple free subset of {a_1, a_2, ..., a_{n}}.


-----Examples-----
Input
6 2
2 3 6 5 4 10

Output
3



-----Note-----

In the sample input one of the possible maximum 2-multiple free subsets is {4, 5, 6}.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Bessie the cow and her best friend Elsie each received a sliding puzzle on Pi Day. Their puzzles consist of a 2<=×<=2 grid and three tiles labeled 'A', 'B', and 'C'. The three tiles sit on top of the grid, leaving one grid cell empty. To make a move, Bessie or Elsie can slide a tile adjacent to the empty cell into the empty cell as shown below:

In order to determine if they are truly Best Friends For Life (BFFLs), Bessie and Elsie would like to know if there exists a sequence of moves that takes their puzzles to the same configuration (moves can be performed in both puzzles). Two puzzles are considered to be in the same configuration if each tile is on top of the same grid cell in both puzzles. Since the tiles are labeled with letters, rotations and reflections are not allowed.

Input Specification:
The first two lines of the input consist of a 2<=×<=2 grid describing the initial configuration of Bessie's puzzle. The next two lines contain a 2<=×<=2 grid describing the initial configuration of Elsie's puzzle. The positions of the tiles are labeled 'A', 'B', and 'C', while the empty cell is labeled 'X'. It's guaranteed that both puzzles contain exactly one tile with each letter and exactly one empty position.

Output Specification:
Output "YES"(without quotes) if the puzzles can reach the same configuration (and Bessie and Elsie are truly BFFLs). Otherwise, print "NO" (without quotes).

Demo Input:
['AB\nXC\nXB\nAC\n', 'AB\nXC\nAC\nBX\n']

Demo Output:
['YES\n', 'NO\n']

Note:
The solution to the first sample is described by the image. All Bessie needs to do is slide her 'A' tile down.

In the second sample, the two puzzles can never be in the same configuration. Perhaps Bessie and Elsie are not meant to be friends after all...

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Consider the following grammar:
-  &lt;expression&gt; ::= &lt;term&gt; | &lt;expression&gt; '+' &lt;term&gt;-  &lt;term&gt; ::= &lt;number&gt; | &lt;number&gt; '-' &lt;number&gt; | &lt;number&gt; '(' &lt;expression&gt; ')'-  &lt;number&gt; ::= &lt;pos_digit&gt; | &lt;number&gt; &lt;digit&gt;-  &lt;digit&gt; ::= '0' | &lt;pos_digit&gt;-  &lt;pos_digit&gt; ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
This grammar describes a number in decimal system using the following rules:
-  &lt;number&gt; describes itself,-  &lt;number&gt;-&lt;number&gt; (l-r, *l*<=≤<=*r*) describes integer which is concatenation of all integers from *l* to *r*, written without leading zeros. For example, 8-11 describes 891011,-  &lt;number&gt;(&lt;expression&gt;) describes integer which is concatenation of &lt;number&gt; copies of integer described by &lt;expression&gt;,-  &lt;expression&gt;+&lt;term&gt; describes integer which is concatenation of integers described by &lt;expression&gt; and &lt;term&gt;.
For example, 2(2-4+1)+2(2(17)) describes the integer 2341234117171717.

You are given an expression in the given grammar. Print the integer described by it modulo 109<=+<=7.

Input Specification:
The only line contains a non-empty string at most 105 characters long which is valid according to the given grammar. In particular, it means that in terms l-r *l*<=≤<=*r* holds.

Output Specification:
Print single integer — the number described by the expression modulo 109<=+<=7.

Demo Input:
['8-11\n', '2(2-4+1)+2(2(17))\n', '1234-5678\n', '1+2+3+4-5+6+7-9\n']

Demo Output:
['891011\n', '100783079\n', '745428774\n', '123456789\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day Polycarp published a funny picture in a social network making a poll about the color of his handle. Many of his friends started reposting Polycarp's joke to their news feed. Some of them reposted the reposts and so on.

These events are given as a sequence of strings "name1 reposted name2", where name1 is the name of the person who reposted the joke, and name2 is the name of the person from whose news feed the joke was reposted. It is guaranteed that for each string "name1 reposted name2" user "name1" didn't have the joke in his feed yet, and "name2" already had it in his feed by the moment of repost. Polycarp was registered as "Polycarp" and initially the joke was only in his feed.

Polycarp measures the popularity of the joke as the length of the largest repost chain. Print the popularity of Polycarp's joke.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 200) — the number of reposts. Next follow the reposts in the order they were made. Each of them is written on a single line and looks as "name1 reposted name2". All the names in the input consist of lowercase or uppercase English letters and/or digits and have lengths from 2 to 24 characters, inclusive.

We know that the user names are case-insensitive, that is, two names that only differ in the letter case correspond to the same social network user.


-----Output-----

Print a single integer — the maximum length of a repost chain.


-----Examples-----
Input
5
tourist reposted Polycarp
Petr reposted Tourist
WJMZBMR reposted Petr
sdya reposted wjmzbmr
vepifanov reposted sdya

Output
6

Input
6
Mike reposted Polycarp
Max reposted Polycarp
EveryOne reposted Polycarp
111 reposted Polycarp
VkCup reposted Polycarp
Codeforces reposted Polycarp

Output
2

Input
1
SoMeStRaNgEgUe reposted PoLyCaRp

Output
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sammy and Simmy love candies and frequently visit the local candy shop. Sammy and Simmy have bought $N$ candy packs. Packet $i$ contains $A_{i}$ candies. Sammy being the elder one is happy only if she has strictly more candies than Simmy. However Simmy, the more sensible one, is happy only if the difference between their number of candies is not more than $1$.

The shopkeeper, being a generous lady, agrees to help Sammy and Simmy by distributing the candies among them in a way that makes both of them happy. The shopkeeper can open the packs and distribute the candies even within a single pack to different people.

------ Input: ------
The first line will contain $T$, the number of testcases.
The first line of every test case will contain $N$, the number of candy packs.
The next line has $N$ integers, the $i_{th}$ integer denoting $A_{i}$, 
the number of candies in the $i_{th}$ pack.

------ Output: ------
Output "YES" if its possible for the shopkeeper to make both the sisters happy otherwise output "NO".  

------ Constraints  ------
$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{3}$
$1 ≤ A_{i} ≤ 100$

----- Sample Input 1 ------ 
1  
2  
5 2
----- Sample Output 1 ------ 
YES
----- explanation 1 ------ 
Sammy gets 4 candies from the first pack.

Simmy gets 1 candy from the first pack and 2 from the second one.

So in total, Sammy has 4, and Simmy has 3. Since Sammy has strictly more candies than Simmy, Sammy is happy. And since the difference is not more then 1, Simmy is also happy. Thus both of them are happy.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The evil Bumbershoot corporation produces clones for gruesome experiments in a vast underground lab. On one occasion, the corp cloned a boy Andryusha who was smarter than his comrades. Immediately Andryusha understood that something fishy was going on there. He rallied fellow clones to go on a feud against the evil corp, and they set out to find an exit from the lab. The corp had to reduce to destroy the lab complex.

The lab can be pictured as a connected graph with n vertices and m edges. k clones of Andryusha start looking for an exit in some of the vertices. Each clone can traverse any edge once per second. Any number of clones are allowed to be at any vertex simultaneously. Each clone is allowed to stop looking at any time moment, but he must look at his starting vertex at least. The exit can be located at any vertex of the lab, hence each vertex must be visited by at least one clone.

Each clone can visit at most <image> vertices before the lab explodes.

Your task is to choose starting vertices and searching routes for the clones. Each route can have at most <image> vertices.

Input

The first line contains three integers n, m, and k (1 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105, 1 ≤ k ≤ n) — the number of vertices and edges in the lab, and the number of clones.

Each of the next m lines contains two integers xi and yi (1 ≤ xi, yi ≤ n) — indices of vertices connected by the respective edge. The graph is allowed to have self-loops and multiple edges.

The graph is guaranteed to be connected.

Output

You should print k lines. i-th of these lines must start with an integer ci (<image>) — the number of vertices visited by i-th clone, followed by ci integers — indices of vertices visited by this clone in the order of visiting. You have to print each vertex every time it is visited, regardless if it was visited earlier or not.

It is guaranteed that a valid answer exists.

Examples

Input

3 2 1
2 1
3 1


Output

3 2 1 3


Input

5 4 2
1 2
1 3
1 4
1 5


Output

3 2 1 3
3 4 1 5

Note

In the first sample case there is only one clone who may visit vertices in order (2, 1, 3), which fits the constraint of 6 vertices per clone.

In the second sample case the two clones can visited vertices in order (2, 1, 3) and (4, 1, 5), which fits the constraint of 5 vertices per clone.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Taru likes reading. Every month he gets a copy of the magazine "BIT". The magazine contains information about the latest advancements in technology.  Taru 

reads the book at night and writes the page number to which he has read on a piece of paper so that he can continue from there the next day. But sometimes 

the page number is not printed or is so dull that it is unreadable.  To make matters worse Taru's brother who is really naughty tears of some of the pages of 

the Magazine and throws them in the dustbin. He remembers the number of leaves he had torn but he does not remember which page numbers got removed. When Taru 

finds this out he is furious and wants to beat him up. His brother apologizes, and says he won't ever do this again. But Taru did not want to be easy on him 

and he says "I will leave you only if you help me find the answer to this. I will tell you how many pages (Printed sides) were there in the Magazine plus the 

pages on which the page numbers were not printed. You already know the number of leaves you tore (T). Can you tell me the expected sum of the page numbers 

left in the Magazine?" Taru's brother replied "huh!! This is a coding problem". Please help Taru's brother.

Note: The magazine is like a standard book with all odd page numbers in front and the successive even page number on its back. If the book contains 6 pages, 

Page number 1 and Page number 2 are front and back respectively. Tearing a leaf removes both the front and back page numbers.


-----Input-----
The first line contains the number of test cases t. 3t lines follow. The first line of each test case contains the number of pages (printed sides) in the 

book. The second line's first integer is F, F integers follow which tell us the numbers of the page numbers not printed. The third line contains a single integer telling us the number of leaves Taru's brother tore.

-----Output-----
Output one real number correct up to 4 decimal digits which is equal to the expected sum of the page numbers left in the book.

-----Constraints-----

Number of printed Sides<=2000. All other values abide by the number of printed sides.

-----Example-----
Input:
2
10
2 1 2
2
10
1 8
0

Output:
31.2000
47.0000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is an advocate for Go Green Initiative. Today he had n trees planted in a row outside his his restaurant. Today, the height of i-th tree is hi feet. The trees grow at a rate of mi feet per day.
Chef knows that trees will look beautiful if they form a zig-zag sequence. The trees will be said to be in Zig-zag sequence if the heights of tree first increases or decreases, then alternates between decreasing/increasing respectively. Formally, the trees will be said to in Zig-zag sequence if one of the following two conditions holds.

- h1 < h2 > h3 < h4 and so on..
- h1 >  h2 < h3 > h4 and so on..

Chef wants to know intervals of time when the heights of the trees will form a zig-zag sequence.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer n, denoting the number of trees.
The ith of following N lines contains two space separated integers hi and mi, denoting the initial height and the growth speed for ith tree.

-----Output-----
For each test case, output an integer Q - the amount of the periods of consecutive moments of time, when the trees for a zig-zag sequence.
On the following Q lines, output the intervals of time when the trees' heights form a zig-zag sequence. For each intervals, output its' smallest and the largest instants of time. If the range is infinite, output Inf as the right bound.
The test cases are designed in such a way that the total output won't exceed 2 MB.

-----Constraints-----

- 1 ≤ T ≤ 105
- 1 ≤ n ≤ 10
- Subtask 1 (23 points): 0 ≤ hi, mi ≤ 10
- Subtask 2 (77 points): 0 ≤ hi, mi ≤ 109
- 1 ≤ sum of n over a test cases in a single test file ≤ 5 × 105

-----Example-----
Input:3
3
0 1
2 2
0 3
2
2 1
1 2
3
1 1
2 2
3 3

Output:1
0 1
2
0 0
2 Inf
0

-----Explanation-----
Example case 1. In the first case 0 2 0 is already a zig-zag sequence, but on the 2nd second it will become 2 6 6 and will never turn back into zig-zag

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Your city has *n* junctions. There are *m* one-way roads between the junctions. As a mayor of the city, you have to ensure the security of all the junctions.

To ensure the security, you have to build some police checkposts. Checkposts can only be built in a junction. A checkpost at junction *i* can protect junction *j* if either *i*<==<=*j* or the police patrol car can go to *j* from *i* and then come back to *i*.

Building checkposts costs some money. As some areas of the city are more expensive than others, building checkpost at some junctions might cost more money than other junctions.

You have to determine the minimum possible money needed to ensure the security of all the junctions. Also you have to find the number of ways to ensure the security in minimum price and in addition in minimum number of checkposts. Two ways are different if any of the junctions contains a checkpost in one of them and do not contain in the other.

Input Specification:
In the first line, you will be given an integer *n*, number of junctions (1<=≤<=*n*<=≤<=105). In the next line, *n* space-separated integers will be given. The *i**th* integer is the cost of building checkpost at the *i**th* junction (costs will be non-negative and will not exceed 109).

The next line will contain an integer *m* (0<=≤<=*m*<=≤<=3·105). And each of the next *m* lines contains two integers *u**i* and *v**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*; *u*<=≠<=*v*). A pair *u**i*,<=*v**i* means, that there is a one-way road which goes from *u**i* to *v**i*. There will not be more than one road between two nodes in the same direction.

Output Specification:
Print two integers separated by spaces. The first one is the minimum possible money needed to ensure the security of all the junctions. And the second one is the number of ways you can ensure the security modulo 1000000007 (109<=+<=7).

Demo Input:
['3\n1 2 3\n3\n1 2\n2 3\n3 2\n', '5\n2 8 0 6 0\n6\n1 4\n1 3\n2 4\n3 4\n4 5\n5 1\n', '10\n1 3 2 2 1 3 1 4 10 10\n12\n1 2\n2 3\n3 1\n3 4\n4 5\n5 6\n5 7\n6 4\n7 3\n8 9\n9 10\n10 9\n', '2\n7 91\n2\n1 2\n2 1\n']

Demo Output:
['3 1\n', '8 2\n', '15 6\n', '7 1\n']

Note:
none

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