vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
During the breaks between competitions, top-model Izabella tries to develop herself and not to be bored. For example, now she tries to solve Rubik's cube 2x2x2.

It's too hard to learn to solve Rubik's cube instantly, so she learns to understand if it's possible to solve the cube in some state using 90-degrees rotation of one face of the cube in any direction.

To check her answers she wants to use a program which will for some state of cube tell if it's possible to solve it using one rotation, described above.

Cube is called solved if for each face of cube all squares on it has the same color.

https://en.wikipedia.org/wiki/Rubik's_Cube


-----Input-----

In first line given a sequence of 24 integers a_{i} (1 ≤ a_{i} ≤ 6), where a_{i} denotes color of i-th square. There are exactly 4 occurrences of all colors in this sequence.


-----Output-----

Print «YES» (without quotes) if it's possible to solve cube using one rotation and «NO» (without quotes) otherwise.


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

Output
NO
Input
5 3 5 3 2 5 2 5 6 2 6 2 4 4 4 4 1 1 1 1 6 3 6 3

Output
YES


-----Note-----

In first test case cube looks like this: [Image] 

In second test case cube looks like this:  [Image] 

It's possible to solve cube by rotating face with squares with numbers 13, 14, 15, 16.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer N. Determine if there exists a tuple of subsets of \\{1,2,...N\\}, (S_1,S_2,...,S_k), that satisfies the following conditions:

* Each of the integers 1,2,...,N is contained in exactly two of the sets S_1,S_2,...,S_k.
* Any two of the sets S_1,S_2,...,S_k have exactly one element in common.



If such a tuple exists, construct one such tuple.

Constraints

* 1 \leq N \leq 10^5
* N is an integer.

Input

Input is given from Standard Input in the following format:


N


Output

If a tuple of subsets of \\{1,2,...N\\} that satisfies the conditions does not exist, print `No`. If such a tuple exists, print `Yes` first, then print such subsets in the following format:


k
|S_1| S_{1,1} S_{1,2} ... S_{1,|S_1|}
:
|S_k| S_{k,1} S_{k,2} ... S_{k,|S_k|}


where S_i={S_{i,1},S_{i,2},...,S_{i,|S_i|}}.

If there are multiple such tuples, any of them will be accepted.

Examples

Input

3


Output

Yes
3
2 1 2
2 3 1
2 2 3


Input

4


Output

No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A recent lab accident resulted in the creation of an extremely dangerous virus that replicates so rapidly it's hard to predict exactly how many cells it will contain after a given period of time. However, a lab technician made the following observations about its growth per millisecond:

The probability of the number of virus cells growing by a factor of ${a}$ is $0.5$.
The probability of the number of virus cells growing by a factor of ${b}$ is $0.5$. 

Given ${a}$, ${b}$, and knowing that initially there is only a single cell of virus, calculate the expected number of virus cells after $\boldsymbol{\boldsymbol{t}}$ milliseconds. As this number can be very large, print your answer modulo $(10^9+7)$.

Input Format

A single line of three space-separated integers denoting the respective values of ${a}$ (the first growth factor), ${b}$ (the second growth factor), and ${t}}$ (the time you want to know the expected number of cells for).

Constraints

$1\leq t\leq10^{18}$  
$1\leq a,b\leq100$  
it is guaranteed that expected value is integer

Output Format

Print the expected number of virus cells after $\boldsymbol{\boldsymbol{t}}$ milliseconds modulo $(10^9+7)$.

Sample Input
2 4 1

Sample Output
3

Explanation

Initially, the virus has one cell. After a millisecond, with probability $0.5$, its size is doubled and, with probability of the other $0.5$ in the sample space, its size grows by ${4}$ times. Thus, the expected number of virus cell after ${1}$ millisecond is $0.5\cdot2\cdot1+0.5\cdot4\cdot1=3\%\ (10^9+7)=3$. Thus, we print $3$ on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While most devs know about [big/little-endianness](https://en.wikipedia.org/wiki/Endianness), only a selected few know the secret of real hard core coolness with mid-endians.

Your task is to take a number and return it in its mid-endian format, putting the most significant couple of bytes in the middle and all the others around it, alternating left and right.

For example, consider the number `9999999`, whose hexadecimal representation would be `98967F` in big endian (the classic you get converting); it becomes `7F9698` in little-endian and `96987F` in mid-endian.

Write a function to do that given a positive integer (in base 10) and remembering that you need to pad with `0`s when you get a single hex digit!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pig is visiting a friend.

Pig's house is located at point 0, and his friend's house is located at point m on an axis.

Pig can use teleports to move along the axis.

To use a teleport, Pig should come to a certain point (where the teleport is located) and choose where to move: for each teleport there is the rightmost point it can move Pig to, this point is known as the limit of the teleport.

Formally, a teleport located at point x with limit y can move Pig from point x to any point within the segment [x; y], including the bounds. [Image] 

Determine if Pig can visit the friend using teleports only, or he should use his car.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of teleports and the location of the friend's house.

The next n lines contain information about teleports.

The i-th of these lines contains two integers a_{i} and b_{i} (0 ≤ a_{i} ≤ b_{i} ≤ m), where a_{i} is the location of the i-th teleport, and b_{i} is its limit.

It is guaranteed that a_{i} ≥ a_{i} - 1 for every i (2 ≤ i ≤ n).


-----Output-----

Print "YES" if there is a path from Pig's house to his friend's house that uses only teleports, and "NO" otherwise.

You can print each letter in arbitrary case (upper or lower).


-----Examples-----
Input
3 5
0 2
2 4
3 5

Output
YES

Input
3 7
0 4
2 5
6 7

Output
NO



-----Note-----

The first example is shown on the picture below: [Image] 

Pig can use the first teleport from his house (point 0) to reach point 2, then using the second teleport go from point 2 to point 3, then using the third teleport go from point 3 to point 5, where his friend lives.

The second example is shown on the picture below: [Image] 

You can see that there is no path from Pig's house to his friend's house that uses only teleports.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The tournament «Sleepyhead-2010» in the rapid falling asleep has just finished in Berland. n best participants from the country have participated in it. The tournament consists of games, each of them is a match between two participants. n·(n - 1) / 2 games were played during the tournament, and each participant had a match with each other participant. 

The rules of the game are quite simple — the participant who falls asleep first wins. The secretary made a record of each game in the form «xi yi», where xi and yi are the numbers of participants. The first number in each pair is a winner (i.e. xi is a winner and yi is a loser). There is no draws.

Recently researches form the «Institute Of Sleep» have found that every person is characterized by a value pj — the speed of falling asleep. The person who has lower speed wins. Every person has its own value pj, constant during the life. 

It is known that all participants of the tournament have distinct speeds of falling asleep. Also it was found that the secretary made records about all the games except one. You are to find the result of the missing game.

Input

The first line contains one integer n (3 ≤ n ≤ 50) — the number of participants. The following n·(n - 1) / 2 - 1 lines contain the results of the games. Each game is described in a single line by two integers xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi), where xi и yi are the numbers of the opponents in this game. It is known that during the tournament each of the n participants played n - 1 games, one game with each other participant.

Output

Output two integers x and y — the missing record. If there are several solutions, output any of them.

Examples

Input

4
4 2
4 1
2 3
2 1
3 1


Output

4 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is teaching his class of N students at Hogwarts. He groups students with the same height together for an activity. Some of the students end up in a groups with only themselves and are saddened by this.

With the help of his magic wand, Chef can increase the height of any student to any value he likes. Now Chef wonders, what is the minimum number of students whose height needs to be increased so that there are no sad students?

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains one integer N — the number of students.
- The second line consists of N space-separated integers H_{1}, H_{2}, \ldots, H_{N} denoting the heights of the students.

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

For each test case, output on a single line the minimum number of students whose heights must to be increased.

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

$1 ≤ T ≤ 5\cdot 10^{4}$
$2 ≤ N ≤ 10^{5}$
$1 ≤ H_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
4
4
1 2 1 2
4
1 2 2 2
3
1 1 1
5
1 2 3 4 5

----- Sample Output 1 ------ 
0
1
0
3

----- explanation 1 ------ 
Test case $1$: The students form $2$ groups each having $2$ students so no change of heights is required.

Test case $2$: Initially the student with height $1$ cannot be paired with anyone else. Chef can increase his height to $2$ and now there is only $1$ group with all the $4$ students in it.

Test case $3$: All students have same height and hence no change of heights is required.

Test case $4$: One possible way is to increase the height of the first student to $5$ and the heights of the second and third students to $4$, hence forming one group of $2$ students and one of  $3$ students. In total, the heights of $3$ students need to be changed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Slime and his $n$ friends are at a party. Slime has designed a game for his friends to play.

At the beginning of the game, the $i$-th player has $a_i$ biscuits. At each second, Slime will choose a biscuit randomly uniformly among all $a_1 + a_2 + \ldots + a_n$ biscuits, and the owner of this biscuit will give it to a random uniform player among $n-1$ players except himself. The game stops when one person will have all the biscuits.

As the host of the party, Slime wants to know the expected value of the time that the game will last, to hold the next activity on time.

For convenience, as the answer can be represented as a rational number $\frac{p}{q}$ for coprime $p$ and $q$, you need to find the value of $(p \cdot q^{-1})\mod 998\,244\,353$. You can prove that $q\mod 998\,244\,353 \neq 0$.


-----Input-----

The first line contains one integer $n\ (2\le n\le 100\,000)$: the number of people playing the game.

The second line contains $n$ non-negative integers $a_1,a_2,\dots,a_n\ (1\le a_1+a_2+\dots+a_n\le 300\,000)$, where $a_i$ represents the number of biscuits the $i$-th person own at the beginning.


-----Output-----

Print one integer: the expected value of the time that the game will last, modulo $998\,244\,353$.


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

Output
1

Input
2
1 2

Output
3

Input
5
0 0 0 0 35

Output
0

Input
5
8 4 2 0 1

Output
801604029



-----Note-----

For the first example, in the first second, the probability that player $1$ will give the player $2$ a biscuit is $\frac{1}{2}$, and the probability that player $2$ will give the player $1$ a biscuit is $\frac{1}{2}$. But anyway, the game will stop after exactly $1$ second because only one player will occupy all biscuits after $1$ second, so the answer is $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The pandemic is upon us, and the world is in shortage of the most important resource: toilet paper. As one of the best prepared nations for this crisis, BubbleLand promised to help all other world nations with this valuable resource. To do that, the country will send airplanes to other countries carrying toilet paper.

In BubbleLand, there are N toilet paper factories, and N airports. Because of how much it takes to build a road, and of course legal issues, every factory must send paper to only one airport, and every airport can only take toilet paper from one factory.

Also, a road can't be built between all airport-factory pairs, again because of legal issues. Every possible road has number d given, number of days it takes to build that road.

Your job is to choose N factory-airport pairs, such that if the country starts building all roads at the same time, it takes the least amount of days to complete them.

Input

The first line contains two integers N (1 ≤ N ≤ 10^4) - number of airports/factories, and M (1 ≤ M ≤ 10^5) - number of available pairs to build a road between.

On next M lines, there are three integers u, v (1 ≤ u,v ≤ N), d (1 ≤ d ≤ 10^9) - meaning that you can build a road between airport u and factory v for d days.

Output

If there are no solutions, output -1. If there exists a solution, output the minimal number of days to complete all roads, equal to maximal d among all chosen roads.

Example

Input


3 5
1 2 1
2 3 2
3 3 3
2 1 4
2 2 5


Output


4

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Iahub recently has learned Bubble Sort, an algorithm that is used to sort a permutation with *n* elements *a*1, *a*2, ..., *a**n* in ascending order. He is bored of this so simple algorithm, so he invents his own graph. The graph (let's call it *G*) initially has *n* vertices and 0 edges. During Bubble Sort execution, edges appear as described in the following algorithm (pseudocode). 

For a graph, an independent set is a set of vertices in a graph, no two of which are adjacent (so there are no edges between vertices of an independent set). A maximum independent set is an independent set which has maximum cardinality. Given the permutation, find the size of the maximum independent set of graph *G*, if we use such permutation as the premutation *a* in procedure bubbleSortGraph.

Input Specification:
The first line of the input contains an integer *n* (2<=≤<=*n*<=≤<=105). The next line contains *n* distinct integers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=*n*).

Output Specification:
Output a single integer — the answer to the problem.

Demo Input:
['3\n3 1 2\n']

Demo Output:
['2\n']

Note:
Consider the first example. Bubble sort swaps elements 3 and 1. We add edge (1, 3). Permutation is now [1, 3, 2]. Then bubble sort swaps elements 3 and 2. We add edge (2, 3). Permutation is now sorted. We have a graph with 3 vertices and 2 edges (1, 3) and (2, 3). Its maximal independent set is [1, 2].

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
According to the regulations of Berland's army, a reconnaissance unit should consist of exactly two soldiers. Since these two soldiers shouldn't differ much, their heights can differ by at most *d* centimeters. Captain Bob has *n* soldiers in his detachment. Their heights are *a*1,<=*a*2,<=...,<=*a**n* centimeters. Some soldiers are of the same height. Bob wants to know, how many ways exist to form a reconnaissance unit of two soldiers from his detachment.

Ways (1,<=2) and (2,<=1) should be regarded as different.

Input Specification:
The first line contains two integers *n* and *d* (1<=≤<=*n*<=≤<=1000,<=1<=≤<=*d*<=≤<=109) — amount of soldiers in Bob's detachment and the maximum allowed height difference respectively. The second line contains *n* space-separated integers — heights of all the soldiers in Bob's detachment. These numbers don't exceed 109.

Output Specification:
Output one number — amount of ways to form a reconnaissance unit of two soldiers, whose height difference doesn't exceed *d*.

Demo Input:
['5 10\n10 20 50 60 65\n', '5 1\n55 30 29 31 55\n']

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

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A boy Petya loves chess very much. He even came up with a chess piece of his own, a semiknight. The semiknight can move in any of these four directions: 2 squares forward and 2 squares to the right, 2 squares forward and 2 squares to the left, 2 squares backward and 2 to the right and 2 squares backward and 2 to the left. Naturally, the semiknight cannot move beyond the limits of the chessboard.

Petya put two semiknights on a standard chessboard. Petya simultaneously moves with both semiknights. The squares are rather large, so after some move the semiknights can meet, that is, they can end up in the same square. After the meeting the semiknights can move on, so it is possible that they meet again. Petya wonders if there is such sequence of moves when the semiknights meet. Petya considers some squares bad. That is, they do not suit for the meeting. The semiknights can move through these squares but their meetings in these squares don't count.

Petya prepared multiple chess boards. Help Petya find out whether the semiknights can meet on some good square for each board.

Please see the test case analysis.

Input Specification:
The first line contains number *t* (1<=≤<=*t*<=≤<=50) — the number of boards. Each board is described by a matrix of characters, consisting of 8 rows and 8 columns. The matrix consists of characters ".", "#", "K", representing an empty good square, a bad square and the semiknight's position, correspondingly. It is guaranteed that matrix contains exactly 2 semiknights. The semiknight's squares are considered good for the meeting. The tests are separated by empty line.

Output Specification:
For each test, print on a single line the answer to the problem: "YES", if the semiknights can meet and "NO" otherwise.

Demo Input:
['2\n........\n........\n......#.\nK..##..#\n.......#\n...##..#\n......#.\nK.......\n\n........\n........\n..#.....\n..#..#..\n..####..\n...##...\n........\n....K#K#\n']

Demo Output:
['YES\nNO\n']

Note:
Consider the first board from the sample. We will assume the rows and columns of the matrix to be numbered 1 through 8 from top to bottom and from left to right, correspondingly. The knights can meet, for example, in square (2, 7). The semiknight from square (4, 1) goes to square (2, 3) and the semiknight goes from square (8, 1) to square (6, 3). Then both semiknights go to (4, 5) but this square is bad, so they move together to square (2, 7).

On the second board the semiknights will never meet.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string, which contains entirely of decimal digits (0-9). Each digit is made of a certain number of dashes, as shown in the image below. For instance 1 is made of 2 dashes, 8 is made of 7 dashes and so on.

You have to write a function that takes this string message as an input and returns a corresponding value in terms of a number. This number is the count of dashes in the string message.

Note:

0 consists of 6 dashes, 1 consists of 2 dashes, 2 consists of 5 dashes, 3 consists of 5 dashes, 4 consists of 4 dashes, 5 consists of 5 dashes, 6 consists of 6 dashes, 7 consists of 3 dashes [though the figure shows that 7 consists of 4 dashes but due to minor mistake in the problem please write your solution assuming 7 consists of 3 dashes], 8 consists of 7 dashes, 9 consists of 6 dashes.

Constraints
String message will contain at least one digit, but not more than 100
Each character in code will be a digit ('0'-'9').

SAMPLE INPUT
12134

SAMPLE OUTPUT
18

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp is a music editor at the radio station. He received a playlist for tomorrow, that can be represented as a sequence a_1, a_2, ..., a_{n}, where a_{i} is a band, which performs the i-th song. Polycarp likes bands with the numbers from 1 to m, but he doesn't really like others. 

We define as b_{j} the number of songs the group j is going to perform tomorrow. Polycarp wants to change the playlist in such a way that the minimum among the numbers b_1, b_2, ..., b_{m} will be as large as possible.

Find this maximum possible value of the minimum among the b_{j} (1 ≤ j ≤ m), and the minimum number of changes in the playlist Polycarp needs to make to achieve it. One change in the playlist is a replacement of the performer of the i-th song with any other group.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ m ≤ n ≤ 2000).

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where a_{i} is the performer of the i-th song.


-----Output-----

In the first line print two integers: the maximum possible value of the minimum among the b_{j} (1 ≤ j ≤ m), where b_{j} is the number of songs in the changed playlist performed by the j-th band, and the minimum number of changes in the playlist Polycarp needs to make.

In the second line print the changed playlist.

If there are multiple answers, print any of them.


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

Output
2 1
1 2 1 2 




Input
7 3
1 3 2 2 2 2 1

Output
2 1
1 3 3 2 2 2 1 




Input
4 4
1000000000 100 7 1000000000

Output
1 4
1 2 3 4 






-----Note-----

In the first sample, after Polycarp's changes the first band performs two songs (b_1 = 2), and the second band also performs two songs (b_2 = 2). Thus, the minimum of these values equals to 2. It is impossible to achieve a higher minimum value by any changes in the playlist. 

In the second sample, after Polycarp's changes the first band performs two songs (b_1 = 2), the second band performs three songs (b_2 = 3), and the third band also performs two songs (b_3 = 2). Thus, the best minimum value is 2.

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