There is a lot of caves in Byteland. This is the map of one of them:

All caves in Byteland have the following properties:

• All the chambers and passages are on the same level.
• No two passages cross each other.
• Some of the chambers are situated on the outer circle. They are called outer chambers.
• All the other chambers lie inside the outer circle and are called inner chambers.
• There is an entrance to the cave leading to one of the outer chambers.
• There are exactly three passages leading from every chamber to three different other chambers. If a chamber is an outer chamber then two of the passages lead to two neighbouring outer chambers on the circle and exactly one leads to an inner chamber.
• Passages connecting outer chambers are called outer passages and the remaining ones are called inner passages.
• It is possible to walk from one chamber to another using only inner passages but there is only one way to do that if we allow to walk through every inner passage at most once.
• Not all passages are equally hard to go through. They are divided into two groups: easy and hard.

Example

Consider the cave showed in the figure. The entrance chamber is 1. The dashed passages are hard to walk through. Route 1, 5, 4, 6, 8, 7, 2, 3 contains no hard passages at all. The final chamber, number 1, is implied and not listed.

Task

Write a program that:

• reads the description of a cave from the text file CAV.IN;
• finds a route through the cave that begins and ends in the entrance chamber, lets the visitors see all the other chambers only once and contains as few hard passages as possible;
• writes the result to the text file CAV.OUT

There are two integers n, k (separated by a single space) in the first line of the text file CAV.IN. The integer n, 3 < n <= 500, is the number of all chambers in a cave and k is the number of all its outer chambers, k >= 3. The chambers are numbered from 1 to n. Chamber 1 is the entrance chamber. Chambers 1, 2, ..., k are outer chambers. They do not have to appear on the outer circle in this order.

The next 3n / 2 lines contain descriptions of the passages. Each description consists of three integers a, b, c separated by single spaces. The integers a and b are numbers of chambers at the ends of a passage. The integer c equals 0 or 1, where 0 means that the passage is easy to walk through and 1 that it is hard.

Output

Your program should write a sequence of n integers separated by single spaces to the first line of the text file CAV.OUT; the sequence has to begin with 1 (the entrance chamber). The following n - 1 integers should be consecutive chambers on the computed route.

Example

For the text file CAV.IN:

  8 5
  1 3 0
  3 2 0
  7 3 1
  7 2 0
  8 7 0
  1 8 0
  6 8 0
  6 4 0
  6 5 1
  5 4 0
  2 4 0
  5 1 0

  1 5 4 6 8 7 2 3

A domino is a flat, thumbsized tile, the face of which is divided into two squares, each left blank or bearing from one to six dots. There is a row of dominoes laid out on a table:

The number of dots in the top line is 6+1+1+1=9 and the number of dots in the bottom line is 1+5+3+2=11. The gap between the top line and the bottom line is 2. The gap is the absolute value of difference between two sums.

Each domino can be turned by 180 degrees keeping its face always upwards.

What is the smallest number of turns needed to minimise the gap between the top line and the bottom line?

For the figure above it is sufficient to turn the last domino in the row in order to decrease the gap to 0. In this case the answer is 1.

Task

Write a program that:

• reads the number of dominoes and their descriptions from the text file DOM.IN,
• computes the smallest number of turns needed to minimise the gap between the top line and the bottom line,
• writes the result to the text file DOM.OUT.

The first line of the text file DOM.IN contains an integer n, 1 <= n <= 1000. This is the number of dominoes laid out on the table.

Each of the next n lines contains two integers a, b separated by a single space, 0 <= a, b <= 6. The integers a and b written in the line i + 1 of the input file, 1 <= i <= 1000, are the numbers of dots on the i-th domino in the row, respectively, in the top line and in the bottom one.

Output

Your program should write exactly one integer to the first line of the text file DOM.OUT; this integer should be the smallest number of turns needed to minimise the gap between the top line and the bottom line.

Example

For the text file DOM.IN:

  4
  6 1
  1 5
  1 3
  1 2

  1

The base of the hexadecimal system is 16. In order to write down numbers in this system one uses 16 digits 0,1,...,9,A,B,C,D,E,F. The capital letters A,..,F stands for 10,..,15, respectively. For instance the value of the hexadecimal number CF2 is 12 * 16² + 15 * 16 + 2 = 3314 in the decimal system. Let X be the set of all positive integers whose hexadecimal representations have at most 8 digits and do not contain repetitions of any digit. The most significant digit in such a representation is not zero. The largest element in X is the number with the hexadecimal representation FEDCBA98, the second largest is the number FEDCBA97, the third is FEDCBA96 and so forth.

Task

Write a program that:

• reads positive integer n from the text file HEX.IN, n does not exceed the number of elements of X;
• finds the n-th largest element of X;
• writes the result to the text file HEX.OUT.

The first line of the file HEX.IN contains integer n in the decimal representation.

Output

Your program should write the n-th largest element in X in the hexadecimal representation to the first line of the text file HEX.OUT

Example

For the text file HEX.IN:

  11

  FEDCBA87

An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b.

Task

Write a program that:

• reads the number of intervals and their descriptions from the text file INT.IN;
• finds the minimal number of elements in a set containing at least two different integers from each interval;
• writes the result to the text file INT.OUT

The first line of the text file INT.IN contains the number of intervals n, 1<=n<=10000. Each of the following n lines contains two integers a, b separated by a single space, 0 <= a < b <= 10000. They are the beginning and the end of an interval.

Output

Your program should write one integer to the first line of the text file INT.OUT; this should be the minimal number of elements in a set containing at least two different integers from each interval.

Example

For the text file INT.IN:

  4
  3 6
  2 4
  0 2
  4 7

  4

Citizens of Byteland adore all sports in which logical thinking is as important as physical skills. One of these sports is crossing the Hex River - the widest river in Byteland. There are n poles numbered 1, ..., n (from left to right) stretching across the river. The citizens have to cross the river by going from the left bank to one pole perhaps to another and so on and then to the right bank. The left bank is located one pole to the left of pole 1; the right bank is located one pole to the right of pole n.

At time 0, the citizen is on the left bank of the Hex River with the goal of reaching the right bank of the river as quickly as possible. At any given time, each pole is either up or down and the citizen is standing on a pole or standing on a bank of the river. A citizen can stand on a pole only if it is up; such a pole is available.

Each pole is down at time 0 and then spends a time units up, b time units down, a time units up, b time units down, etc. The constants a and b are defined separately for each pole. For example the pole with a=2 and b=3 will be down at time 0, up at time 1 and 2, down at time 3, 4, 5 and so on.

At time t+1, a citizen can choose to be on any available pole or river bank within 5 poles of his location at time t or even to stay on his current pole (if available) or bank. For example from pole 5 you can reach any of the poles 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 or the left bank.

Task

Write a program that:

• reads the number of data blocks from the text file RIV.IN (each block contains a complete set of data for the problem);
• for each block
• reads the number of poles and descriptions of their behaviour;
• computes the first possible time the citizen can stand on the right bank, if it is reachable;
• writes the result to the text file RIV.OUT.

The first line of the input file RIV.IN contains the number of data blocks x, 1 <= x <= 5. The following lines comprise the x blocks. The first block starts on the second line of the input file; each subsequent block starts directly after the previous one.

The first line of each block contains an integer n, 5 < n <= 1000, the number of poles.

Each of the following n lines in the block contains two integers a, b separated by a single space, 1 <= a, b <= 5. The integers in line i + 1 (in the block), 1 <= i <= n, describe the behaviour of the pole i.

Output

For the k-th block, 1 <= k <= x, write to the k-th line of the text file RIV.OUT the first time the citizen can reach the right bank or the word NO, when such a crossing is impossible.

Example

For the text file RIV.IN:

  2
  10
  1 1
  1 1
  1 1
  1 1
  1 1
  1 1
  1 1
  1 1
  1 1
  1 1
  10
  1 1
  1 1
  1 1
  1 1
  2 1
  1 1
  1 1
  1 1
  1 1
  1 1

  NO
  4

Welcome to the Annual Byteland Shooting Contest. Each competitor will shoot to a target which is a rectangular grid. The target consists of r*c squares located in r rows and c columns. The squares are coloured white or black. There are exactly two white squares and r-2 black squares in each column. Rows are consecutively labelled 1,..,r from top to bottom and columns are labelled 1, ..., c from left to right. The shooter has c shots.

A volley of c shots is correct if exactly one white square is hit in each column and there is no row without white square being hit. Help the shooter to find a correct volley of hits if such a volley exists.

Example

Consider the following target:

Volley of hits at white squares in rows 2, 3, 1, 4 in consecutive columns 1, 2, 3, 4 is correct.

Task

Write a program that:

• reads the number of data blocks from the text file SHO.IN; each block contains a complete set of data for the problem;
• for each block
• reads the target size and the layout of white squares;
• verifies whether any correct volley of hits exists and if so, finds one of them;
• writes the result to the text file SHO.OUT;

The first line of the input file SHO.IN contains the number of data blocks x, 1 <= x <= 5. The following lines constitute x blocks. The first block starts in the second line of the input file; each next block starts directly after the previous one.

The first line of each block contains two integers r and c separated by a single space, 2 <= r <= c <= 1000. These are the numbers of rows and columns, respectively. Each of the next c lines in the block contains two integers separated by a single space. The integers in the input line i + 1 in the block, 1 <= i <= c, are labels of rows with white squares in the i-th column.

Output

For the i-th block, 1 <= i <= x, your program should write to the i-th line of the file SHO.OUT either a sequence of c row labels (separated by single spaces) forming a correct volley of hits at white squares in consecutive columns 1, 2, ..., c, or one word NO if such a volley does not exists.

Example

For the text file SHO.IN:

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

  2 3 1 4
  NO