1994		Cluj, Romania, May 27 - 31
1995		Szeged, Hungary, May 29 - June 3
1996		Bratislava, Slovakia, October 9 - 13
1997		Nowy Sacz, Poland, July 17 - 24
1998		Zadar, Croatia, May 20 - 27
1999		Brno, Czech Republic, September 2 - 9
2000		Cluj, Romania, August 24 - 31
2001		Zalaegerszeg, Hungary, August 10 - 17
2002		Košice, Slovakia, June 30 - July 6
2003		Muenster, Germany

For the purposes of computer graphics a part of the screen is always coded by a positive integer consisting only of digits 1, 2, 3, 4. See the pictures:

Normalised square * is coded by 133, normalised square + is coded by 343. There is no limit on the scale of the normalised squares. If you want to shift square * to the place +, you may shift it for example 4 times down and then 2 times to the right.

Write a program into the file SQUARE.PAS which does repeatedly the following:

a) Reads a code of a normalised square from one line of the input file SQUARE.DAT as a positive integer, consisting only of digits 1,2,3,4 and a sequence of shifts L (left), R (right), U (up), D (down) as a sequence of letters L, R, U, D from the next line of the input file SQUARE.DAT.

b) Writes the final position of the normalised square into the output file SQUARE.RES or writes message

OUT OF THE BORDER

c) Writes an empty line into the output file SQUARE.RES, until an empty line is read.

In each data set, the number of digits in the code is less or equal to 35.

The time limit is at most 1 minute for each data set.

Example

If the file SQUARE.DAT contains

  133
  DDDDRR
  1
  DD

the output file SQUARE.RES should contain

  343

Let n be a positive integer. We consider an ordering <, called lexicographic ordering, defined on the subsets of {1,2,...,n}. Let S₁ = {x₁,...,x_i} and S₂ = {y₁,...,y_j} be two distinct subsets of {1,2,...,n} with x₁<x₂<...<x_i and y₁<y₂<...<y_j. Then we say that S₁<S₂ if there exists k with 0<=k<=min{i,j} such that x₁=y₁,...,x_k=y_k and either k=i or x_k+1<y_k+1.

For example, the subsets of {1,2,3} listed in lexicographic order are:

  {}          1
  {1}         2
  {1,2}       3
  {1,2,3}     4
  {1,3}       5
  {2}         6
  {2,3}       7
  {3}         8

The lexicographic ordering associates to each subset a natural number, as shown in the above example.

Your program should read lines from an ASCII file called P6.TXT. Each line has one of the following forms:

  1 n k
  2 n k1 k2 . . . ki

If the line has the first form, you have to print on the display the subset of {1,2,...,n} whose associated number is k (supposing that k<=2ⁿ).

If the line is of the second form, you have to print the number associated with the subset {k1,...,ki} of {1,...,n} (supposing that 1<=k1<k2< ...<ki<=n).

Your program should be able to produce the answer for each input line in at most 3 minutes, assuming that n<=30.

We construct objects according to the following rules:

1. The initial object is a square with the side equal to 1;

2. A new object is obtained concatenating two objects on the side which has the same length.

3. Each time a new object is constructed, it is supposed that an infinite instances of this object are available.

Requirements:

1) A positive integer n is introduced from the keyboard. Display the number of objects having the area at most n, which can be constructed if only two objects of the same dimensions will be concatenated. Two objects with the same dimensions are conside"#008DDC" identical. For example, a valid output for n=20 is:

  (1,1) (2,1) (4,2) (8,2) (16,3)

where in each pair the first number represents the area of an object and the second one represents the number of distinct objects having this area.

2) The same requirements must be satisfied when we are allowed to concatenate objects of different dimensions, according to the rules 1 - 3. For example, a valid output for n=10 is:

  (1,1) (2,1) (3,1) (4,2) (5,1) (6,2) (7,1) (8,2) (9,2) (10,2)

the pairs having the same meaning as in requirement 1).

The input is a single line introduced from the keyboard, containing a pair:

  i n

where i is a member of {1,2}, meaning the number of the requirement and n is the above specified integer number.

The output is a text file containing pairs of elements, as shown above.

The maximum value for n is 10000. Your program should be able to produce the answer for each data test in at most 1 minute.

Write a program which reads three positive integers n, p, q. Decide whether or not there exists a sequence of n integers such that the sum of any p consecutive elements is positive and the sum of any q consecutive ones is negative. If the answer is YES, your program has to produce such a sequence.

The values of n, p, q are read from the keyboard; the output consists of NO or YES followed by a sequence of n integers written on display.

Example 1

If the input is

  n=4
  p=2
  q=3

the output is

  NO

Example 2

If the input is

  n=6
  p=5
  q=3

  YES
  -3 5 -3 -3 5 -3

Let us consider a country with N towns. A system of roads formed from direct connections between towns is given; all these direct connections are conside"#008DDC" to have the length equal to 1. This system is called even-odd if there are two towns linked by a road of even length, as well as by a road of odd length.

a) Find out if the system of roads is even-odd or not.

b) If the answer for a) is negative, find one of the subsets X of towns which has a maximal number of elements and satisfies the following condition: for any two towns in X, if there is a path linking them, then its length is even.

The name of the input file is introduced from the keyboard. Its first line contains the value of N; the following lines contain pairs I, J with the meaning that the towns I and J are directly linked.

The value of N is at most 300.

Display the output on the screen in an intelligible form.

Examples

If the input file contains

  1 2
  2 3
  3 4
  4 5
  5 1

  YES

  1 2

  NO
  X has 2 elements X: 2 3

An expression contains additions and multiplications. The time needed to evaluate an addition (+) is p and the time needed for a multiplication (*) is q. The time needed to evaluate the expression AoB is equal to the time needed to evaluate the operation o plus the maximum of the times needed to evaluate the subexpressions A, and B respectively.

The operands are variables consisting of a single character, whose evaluation time is conside"#008DDC" as being equal to 0.

Write a program which reads data from an input file that contains the values of p and q and expressions, each expression on a separate line. The parentheses are used compulsory to indicate the order of operations. For each expression one asks:

a) To find and print the time needed to evaluate that expression;

b) To find and print an equivalent arithmetic expression with a minimum evaluation time, as well as this minimum evaluation time on next line.

The equivalent transformations permitted are:
x+y=y+x, x*y=y*x (commutativity)
and
x+(y+z)=(x+y)+z, x*(y*z)=(x*y)*z (associativity).

The results must be printed in the output file that contains an empty line between two expressions.

For example,

if the input file contains:

  1 1
  ((a+(b+(c+d)))*e)*f
  ((((a*b)*c)*d)+e)+(f*g)

  5
  ((a+b)+(c+d))*(e*f)
  3

  5
  (((a*b)*(c*d))+e)+(f*g)
  4

A computer records the starting and finishing time of each application program in the measure of 1/100 seconds. A daily statistic is a set of pairs (a, b) of non negative integers such that 0<a<=b<8640000. The pair (a, b) means that a program started at time a and finished at time b. The time points a and b belong to busy time. Arbitrary number of programs can run in parallel. Write a program that computes
a) the length (b-a+1) of the largest closed time interval when the machine was idle
and
b) the length (d-c+1) of the largest closed time interval when the machine executed at least one program.
A time point t belongs to the idle time if there is no program running at time t.

Input data

The first line of text file DAY1A.DAT contains N, the number of the intervals (1<=N<=1000). Each of the rest N lines of the file contains two non negative integers, the starting and finishing time of a program.

Output Data

The text file DAY1A.SOL has to contain the following two integers in this order:

a) The length (b-a+1) of the largest interval of time when the machine was idle.

b) The length (d-c+1) of the largest closed time interval when the machine executed at least one program.

Example input

  9
  30000 35000
  10000 20000
  15000 16000
  40000 44000
  77000 220000
  13000 41000
  60000 67000
  50000 55000
  65000 70000

Example output

In our example input the DAY1A.SOL file contains the following two lines:

  8419999
  143001

The students of a class have decided to form an alarm chain. Every student chooses a unique successor, to whom he directly delivers received messages. Whenever a student receives a message forwards it to his or her successor.

Such an assignment is called an alarm chain if the following holds. Suppose somebody sends a message to his or her successor, who in turns transmits the message to his or her successor, etc. The message eventually arrives to every student, including the starting student.

Clearly, not every assignment is alarm chain. Write a program which for an arbitrary input assignment, computes the minimal number of necessary modifications that transforms the input assignment to an alarm chain.

Input data

The first line of the text file DAY1B.DAT contains N, the number of the students (1<=N<256). Each of the following N lines contains two names (strings) separated by the character '>'. The second name terminated by end-of-line character. The names are at most 20 characters long. A line of the form A>B means that the successor of student A is B, i.e. A directly delivers messages to B.

Output Data

Write the minimal number of necessary modifications to the text file DAY1B.SOL as an integer.

Example input

  10
  Anita>Peter
  Andrew>Julia
  David>Andrew
  Natalie>Gabriella
  Edith>David
  Peter>Anita
  Gabriella>Julius
  Adam>David
  Julia>Gabriella
  Julius>Julia

Example output

  4

Two brothers, Alan and Bob want to share a set of gifts. Each of the gifts should be given to either Alan or Bob, and none of the gifts can be split. Each gift has a positive integer value. Let A and B denote the total value of gifts received by Alan and Bob, respectively. The aim is to minimise the absolute value of the difference A-B. Write a program which computes the values A and B.

Input data

The first line of the text file DAY1C.DAT contains N, the number of the gifts (1<=N<= 100). The rest of the input contains N positive integers, the values of the gifts. Each value is <=200.

Output Data

Write the two integers A and B to the text file DAY1C.SOL.

Example input

  7
  28 7 11 8 9 7 27

Example output

  48 49

There are N trees in a garden. The shape of the garden is square with 1000 m long sides. We are looking for a rectangle with largest area that does not contain trees inside. The sides of the rectangle must be parallel to the corresponding sides of the garden. Each side of the rectangle may contain trees and may lie on a side of the garden. Trees are given by (x,y) co-ordinates of their positions measu"#008DDC" in meter. A tree is conside"#008DDC" to be a point without extension.

The origin of the co-ordinate system is the lower left corner of the garden and the axes are parallel to the sides.

Input data

The first line of text file DAY2A.DAT contains N, the number of the trees (1<=N<=600). In each of the next N lines you will find integer co-ordinates (x, y) (0<x<1000, 0<y<1000), the positions of the trees.

Output Data

Write the area of the largest rectangle as an integer value in the text file DAY2A.SOL.

Example input

  7
  280 100
  200 600
  400 200
  135 800
  800 400
  600 800
  900 210

Example output

  360000

The president of a company is organising a party for his employees. The company has a hierarchical structure; that is, the supervisor relation forms a tree rooted at the president. In order to make the party fun for all attendees, the president does not want both an employee and his or her supervisors to sit at the same table.

The problem is to compute the minimal number of tables necessary to make a seating arrangement that satisfies the above requirement. The input of the program is the immediate supervisor relation of the company. The supervisor relation is defined in terms of the immediate supervisor relation as follows. A person P is supervisor of a person Q if P is the immediate supervisor of Q, or there are persons P₁, ..., P_k (1<k) such that P=P₁, Q=P_k and P_i is the immediate supervisor of P_i+1 (i=1, ..., k-1).

The number of attendees is N (1<=N<=200), and there are T (2<=T<=10) seats at each table.

Input data

The employees of the company are identified by the first N (1<=N<=200) natural numbers. The president of the company is identified by number 1, and has no supervisor. The first line of the text file DAY2B.DAT contains T, the number of seats per table (2<=T<=10). The second line contains the number N (1<=N<=200) of the attendees, each employee identified by numbers from 1 to N will attend the party. In the third line you find N numbers. The i-th number in the line is the immediate supervisor of the i-th person. The first number in the line is 0, indicating that the president has no supervisor.

Output Data

Write the minimal number of tables needed to seat all attendees in the specified way in the text file DAY2B.SOL.

Example input

  4
  13
  0 1 9 9 9 2 2 1 1 7 8 8 10

Example output

  5

We are given three glasses. The volume of each glass is 100 unit (cm³). The first two glasses have marks, same on both glasses, each mark indicating the volume measu"#008DDC" from the bottom up to the mark. That volume is written beside the mark.

Initially the first glass contains 100 unit volume of fluid, and the others are empty. Write a program that decides whether one unit volume of fluid can be separated in the third glass, and if so, computes the minimal number of steps needed to do it. In each step, after the operation at least one of the used glass must contain fluid up to a mark or empty. During the procedure we can keep track of the actual contents of each three glasses.

Input data

The first line of the text file DAY2C.DAT contains N, the number of the marks on the first two glasses (1<=N<=20). The rest of the file contains N integers in increasing order; that is the volumes corresponding to the marks on the glasses. For each volume mark V the inequalities (1<=V<=100) hold and the largest value is 100.

Output Data

Write the string YES into the first line of the text file DAY2C.SOL if one unit can be separated in the third glass and write NO otherwise. If the answer is yes for the first question then write the minimal number of steps in the second line.

Example input

  4
  13 37 71 100

Example output

  YES
  8

A kind of grid is sometimes used for encoding messages. Our naval fleet officials decide to use this kind of encoding messages for communication with their ship captains. The encoding grid is a square sheet of paper divided into 2N x 2N little squares. N² of little squares are cut out (see figure 1).

Let us briefly describe the encoding process. Take text of message of length 4N². Then put an encoding grid onto a blank sheet of paper and begin to write first N² letters of message into the cut little squares (one letter per square, write letters in all cut squares in the first line from left to right, then in the second line etc.). See example on figure 2 for message "HELLOYELLOWWORLD". After finishing the first step rotate the encoding grid 90 degrees clockwise and continue similarly writing letters. After two more steps all letters should be written (see example on figure 3).

    O###                H###                 HOOY
    ##O#                ##E#                 LREO
    O##O                L##L                 LWEL
    ####                ####                 LLDW

  (fig. 1)            (fig. 2)             (fig. 3)

It is necessary to have a correctly constructed grid. It means that when it is used in the way described above after each rotation new N² blank squares will appear under cut squares of the grid.

The naval fleet officials encoded thousands of messages with their grid and then they wanted to send them to ships. Unfortunately they lost the grid. Fortunately the naval admiral remembe"#008DDC" the original text of one of the messages.

Your task is to get this original message text and encoded text and find one possible correctly constructed encoding grid with which the message text could have been encoded.

Input Data

The first line of input file contains an integer N (1<=N<=10). The second line contains 4N² capital letters representing the original message. The next 2N lines contain the encoded text (each line 2N capital letters).

Output Data

The output file contains a correctly constructed grid with which given message could have been encoded. In each of 2N lines one line of grid (2N characters) will be displayed where "O" (capital letter 'O' represents cut square and "#" uncut square).

Example

GRID.IN

  2
  HELLOYELLOWWORLD
  HOOY
  LREO
  LWEL
  LLDW

  O###
  ##O#
  O##O
  ####

The Palmia country is divided by a river into the north and south bank. There are N towns on both the north and south bank. Each town on the north bank has its unique friend town on the south bank. No two towns have the same friend.

Each pair of friend towns would like to have a ship line connecting them. They applied for permission to the government. Because it is often foggy on the river the government decided to prohibit intersection of ship lines (if two lines intersect there is a high probability of ship crash).

Your task is to write a program to help government officials decide to which ship lines they should grant permission to get maximum number of non intersecting ship lines.

Input Data

The input file consists of several blocks. In the first line of each there are 2 integers X,Y separated with exactly one space, X represents the length of the Palmia river bank (10 <= X <= 6000), Y represents the width of the river (10 <= Y <= 100). The second line contains the integer N, the number of towns situated on both south and north riverbanks (1 <= N <= 5000). On each of the next N lines there are two non-negative integers C,D separated with space (C,D <= X), representing distances of the pair of friend towns from the western border of Palmia measu"#008DDC" along the riverbanks (C for the town on the north bank, D for the town on the south bank). There are no two towns on the same position on the same riverbank. After the last block there is a single line with two numbers 0 separated by a space.

Output Data

For each block of the input file the output file has to contain in consecutive lines the maximum possible number of ship lines satisfying the conditions above.

Example

SHIPS.IN

  30 4
  7
  22 4
  2 6
  10 3
  15 12
  9 8
  17 17
  4 2
  0 0

  4

In Palmia country they have N cities connected by highways (each highway connects exactly two cities in both directions). It is possible to reach every city from any other city using one or several highways. Till this year the highway tolls were collected on highways. In the middle of each highway there was a toll collector who collected 1 Palmia Coin (1 PC) from each car passing by.

Government officials decided to "#008DDC"uce the number of toll collectors and introduce highway stamps. If a car will want to enter a highway it must have this higway stamp placed on the window.

Officials decided that the highway stamp for one year will cost the same as 100 travels between two farthest cities. The distance between two cities is the minimum number of highways you need to use to get from the first city to the second one.

Your task is to write a program which computes the cost of the highway stamp.

Input Data

The input file consists of several blocks of data. Each block at the first line contains the integers N and M separated by a space where N is the number of cities and M the number of highways in Palmia country (1<= N <= 1000, 1 <= M <= 2000). Cities are numbe"#008DDC" by integers from 1 to N. The next M lines contain each one pair of integers A,B (1<= A,B <= N) separated by a space representing that there is a highway between the cities A and B. After the last block there is a single line with two numbers 0 separated by a space.

Output Data

For each block of input file the output file contains a single line with the cost of the highway stamp.

Example

TOLLS.IN

  4 4
  1 2
  2 3
  4 2
  3 4
  0 0

  200

A factory has a bin packing robot at the end of an assembly line. There are exactly two bins open, and the robot packs items into any one of the open bins, one by one sequentially. The bins are identical, and one bin can accommodate a set of items up to a given weight limit. More precisely, the robot can perform the following four instructions:

• Pack the current item into bin 1.
• Pack the current item into bin 2.
• Close bin 1 and open a new empty bin in place of the closed bin.
• Close bin 2 and open a new empty bin in place of the closed bin.

A pack instruction can only be executed if the weight of the current item plus the sum of the weights of the items already in the bin does not exceed the limit. You are given the sequence of weights of items and a weight limit that is constant for all the bins. Write a program that computes the minimal number of bins needed by the robot to pack all items into them.

Input Data

The input file contains integer numbers. The first line of input file contains the weight limit L (1 <= L <= 100). This limit applies to all bins. The second line contains the number of items N (1 <= N <=5000). Each of the following N lines contains the weight of an item. Each weight is at least 1 and at most L.

Output Data

Write on the first line of output file the minimum number of bins needed to pack all items.

Example

BINPACK.IN

  8
  6
  4
  2
  5
  3
  5
  4

  3

You are given a rectangle whose side lengths are integer numbers. You want to cut the rectangle into the smallest number of squares, whose side lengths are also integer numbers. Cutting can be performed with a cutting machine that can cut only from side to side across, parallel with one side of the rectangle. Obtained rectangles are cut separately.

Input Data

The input file contains two positive integers in the first line: the lengths of the sides of the rectangle. Each side of the rectangle is at least 1 and at most 100.

Output Data

The output file consist of one line on which your program should write the number of squares resulting from an optimal cutting.

Example

CUTS.IN

  5 6

  5

The electrician Fero has just finished the installation of the new cable in the building of the CEOI secretariat. The cable consists of N wires and connects the computer room and CEOI secretary office. In the computer room Fero labeled the wires with numbers from 1 to N from left to right. Because the cable was long, sometimes some of wires crossed between the computer room and the office (each pair of wires crosses at most once; at each moment only neighbouring wires may cross). So in the office the wires were not orde"#008DDC" the same way (see figure 1).

To know how these wires are crossed Fero drew the graph on the wall near the cable end in the computer room. The vertices represented wires and edges represented wire crosses. There is an edge between vertices a and b if and only if the wires a and b are crossed somewhere on the way (see figure 2 for graph representing situation in figure 1).

The cable does not function properly now. Unfortunately Fero broke his leg yesterday. We have another electrician but he is not so experienced in graph theory. He needs to know the order of wires at the end of the cable in the CEOI secretary office to correct this fault.

Input Data

In the input file there are several blocks of data. The first line of each block contains two numbers N and M separated by a space, where N (1<= N <= 100) is the number of wires in the cable and M is the number of wire crosses. This is followed by M lines each containing pair of integers A, B separated by a space (1 <= A,B <= N) representing the cross of cable wires A and B somewhere on the way. After the last block there is a line with two numbers 0.

Output Data

For each block of the input file the output file contains a single line with the list of wire numbers in order as they appear at the second end of the cable (N numbers separated by space) or the message "IMPOSSIBLE" if no order is represented by given graph.

Example

ELECTRIC.IN

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

  3 2 4 1 5

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.

It has been decided to open all the caves to the public. To assure a "smooth" and safe flow through a cave, visitors should follow a route marked in advance and visit every chamber of this cave exactly once. An exception from this rule is the entrance chamber where every tour begins and ends, you are allowed to visit this chamber exactly twice. The tour route should be fit for an average visitor and contain as few hard passages to walk through as possible.

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

Input

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 numbe"#008DDC" 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.

Input

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.

Input

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, 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

Input

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 numbe"#008DDC" 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.

Input

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 colou"#008DDC" 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;

Input

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

We are given N squares in the coordinate plane whose sides are parallel to the coordinate axes. All the corners have integer coordinates and the squares do not touch or overlap.

You are requi"#008DDC" to count the number of squares visible from the origin point O, O = (0,0).

A square is visible from the origin point O if there are two distinct points A and B on one of its sides such that the interior of the triangle OAB has no common points with any of the remaining squares.

Input data

The first line of the input file SQUARES.IN contains the integer N, 1<=N<=1000, the number of squares.

Each of the following N lines describes a square by specifying integers X, Y and L separated by single blank characters, 1<=X,Y,L<=10000. X and Y are coordinates of the lower left corner (the corner with the least X and Y coordinates) and L is the side length.

Output data

The first and the only line of the output file SQUARES.OUT should contain the number of squares that are visible from the origin.

Examples

SQUARES.IN

  3
  2 6 3
  1 4 1
  3 4 1

  3

  4
  1 2 1
  3 1 1
  2 4 2
  3 7 1

  2

Alice and Bob have a set of N cards labelled with numbers 1 ... N (so that no two cards have the same label) and a shuffle machine. We assume that N is an odd integer.

The shuffle machine accepts the set of cards arranged in an arbitrary order and performs the following operation of double shuffle: for all positions i, 1<=i<=N, if the card at the position i is j and the card at the position j is k, then after the completion of the operation of double shuffle, position i will hold the card k.

Alice and Bob play a game. Alice first writes down all the numbers from 1 to N in some random order: a₁, a₂, ..., a_N. Then she arranges the cards so that the position a_i holds the card numbe"#008DDC" a_i+1, for every 1<=i<=N-1, while the position a_N holds the card numbe"#008DDC" a₁.

This way, cards are put in some order x₁, x₂, ..., x_N, where x_i is the card at the i^th position.

Now she sequentially performs S double shuffles using the shuffle machine described above. After that, the cards are arranged in some final order p₁, p₂, ..., p_N which Alice reveals to Bob, together with the number S. Bob's task is to guess the order x₁, x₂, ..., x_N in which Alice originally put the cards just before giving them to the shuffle machine.

Input data

The first line of the input file CARDS.IN contains two integers separated by a single blank character: the odd integer N, 1<=N<=1000, the number of cards, and the integer S, 1<=S<=1000, the number of double shuffle operations.

The following N lines describe the final order of cards after all the double shuffles have been performed such that for each i, 1<=i<=N, the (i+1)^st line of the input file contains p_i (the card at the position i after all double shuffles).

Output data

The output file CARDS.OUT should contain N lines which describe the order of cards just before they were given to the shuffle machine.

For each i, 1<=i<=N, the i^th line of the output file should contain x_i (the card at the position i before the double shuffles).

Examples

CARDS.IN

  5 2
  4
  1
  5
  3
  2

  2
  5
  4
  1
  3

  7 4
  6
  3
  1
  2
  4
  7
  5

  4
  7
  5
  6
  1
  2
  3

We are given a sequence of N positive integers a = [a₁, a₂, ..., a_N] on which we can perform contraction operations.

One contraction operation consists of replacing adjacent elements a_i and a_i+1 by their difference a_i-a_i+1. For a sequence of N integers, we can perform exactly N-1 different contraction operations, each of which results in a new (N-1) element sequence.

Precisely, let con(a,i) denote the (N-1) element sequence obtained from by replacing the elements a_i and a_i+1 by a single integer a_i-a_i+1:

  con(a,i) = 

For example, applying contractions 2, 3, 2 and 1 in that order to the sequence con( con( con( Given a sequence a₁, a₂, ..., a_N and a target number T, the problem is to find a sequence of N-1 contractions that applied to the original sequence yields T.

Input data

The first line of the input file SUBTRACT.IN contains two integers separated by blank character: the integer N, 1<=N<=100, the number of integers in the original sequence, and the target integer T, -10000<=T<=10000.

The following N lines contain the starting sequence: for each i, 1<=i<=N, the (i+1)^st line of the input file contains integer a_i, 1<=a_i<=100.

Output data

Output file SUBTRACT.OUT should contain N-1 lines, describing a sequence of contractions that transforms the original sequence into a single element sequence containing only number T. The i^th line of the output file should contain a single integer denoting the i^th contraction to be applied.

You can assume that at least one such sequence of contractions will exist for a given input.

Examples

SUBTRACT.IN

  4 5
  10
  2
  5
  2

  1
  2
  1

  5 4
  12
  10
  4
  3
  5

  2
  3
  2
  1

N soldiers of the land Gridland are randomly scatte"#008DDC" around the country.

A position in Gridland is given by a pair (x,y) of integer coordinates. Soldiers can move - in one move, one soldier can go one unit up, down, left or right (hence, he can change either his x or his y coordinate by 1 or -1).

The soldiers want to get into a horizontal line next to each other (so that their final positions are (x,y), (x+1,y), ..., (x+N-1,y), for some x and y). Integers x and y, as well as the final order of soldiers along the horizontal line is arbitrary.

The goal is to minimise the total number of moves of all the soldiers that takes them into such configuration.

Two or more soldiers must never occupy the same position at the same time.

Input data

The first line of the input file SOLDIERS.IN contains the integer N, 1<=N<=10000, the number of soldiers.

The following N lines of the input file contain initial positions of the soldiers: for each i, 1<=i<=N, the (i+1)^st line of the input file contains a pair of integers x separated by a single blank character, representing the coordinates of the i^th soldier, -10000<=x<=10000.

Output data

The first and the only line of the output file SOLDIERS.OUT should contain the minimum total number of moves that takes the soldiers into a horizontal line next to each other.

Examples

SOLDIERS.IN

  3
  1 0
  2 4
  3 2

  4

  5
  1 2
  2 2
  1 3
  3 -2
  3 3

  8

N cities named with numbers 1 ... N are connected with one-way roads. Each road has two parameters associated with it: the road length and the toll that needs to be paid for the road (expressed in the number of coins).

Bob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away - to the city N. He wants to get there as quickly as possible, but he is short on cash.

We want to help Bob to find the shortest path from the city 1 to the city N that he can afford with the amount of money he has.

Input data

The first line of the input file ROADS.IN contains the integer K, 0<=K<=10000, maximum number of coins that Bob can spend on his way.

The second line contains the integer N, 2<=N<=100, the total number of cities.

The third line contains the integer R, 1<=R<=10000, the total number of roads.

Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters:

• S is the source city, 1<=S<=N
• D is the destination city, 1<=D<=N
• L is the road length, 1<=L<=100
• T is the toll (expressed in the number of coins), 0<=T<=100

Output data

The first and the only line of the output file ROADS.OUT should contain the total length of the shortest path from the city 1 to the city N whose total toll is less than or equal K coins.

If such path does not exist, only number -1 should be written to the output file.

Examples

ROADS.IN

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

  11

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

  -1

Professor Balltazar is a big football fan. His birthday was just a couple of days before he was going to leave for the World Cup Football '98 in France, so his friends gave him as a present a dodecahedron-shaped puzzle as an entertainment while watching the boring games.

The puzzle has 12 equal pentagon sides, labelled with numbers 1, ..., 12. The figure below shows the two hemispheres of the dodecahedron, together with the side labelling we will use in this problem. Hemispheres are "glued" together in such a way that the side 7 is adjacent to the sides 8, 12, 11, 2 and 6 (sides are adjacent if they share an edge). In particular, edges a and b on the left hemisphere will be glued to the edges a and b on the right hemisphere shown below.

In addition to that, there are 12 pentagon-shaped tiles, also labelled from 1 to 12. Every edge on each of the tiles is marked with a number from the set {0, 1, 2}. Each tile can be placed on each of the twelve sides in any of the 5 positions obtained by rotating the tile around its centre.

To solve the puzzle, we need to put each tile on some of the twelve dodecahedron sides in some position, so that every two adjacent tiles have their common edge marked with the same number.

Help Professor Balltazar to solve the puzzle!

Input data

The input file BALL.IN contains 12 lines. For each i, 1<=i<=12, the i^th line describes the i^th tile by specifying 5 numbers from the set {0, 1, 2} separated by single blank characters. This sequence shows the edge marking of the i^th tile starting from an arbitrary edge (called the i^th reference edge) going in the clockwise direction.

Output data

Output file BALL.OUT should contain the description of a solved puzzle in 12 lines with 2 integers in each line. For each i, 1<=i<= 12, the i^th line should contain integers t separated by a single blank character describing the tile and its position on the i^th side:

The i^th side will hold the tile labelled t.

The tile can be placed on the i^th side in five different positions. The exact position is specified by n, which denotes the label of the adjacent side which is in the direction of the t^th reference edge (looking from the centre of the i^th side). Precisely, the t^th reference edge is placed on the dodecahedron edge sha"#008DDC" by the sides labelled i and n.

If the puzzle can not be solved, only number -1 should be written to the output file.

Examples

BALL.IN

  0 0 1 1 2
  0 2 1 0 1
  2 0 1 0 1
  0 0 1 2 1
  0 2 1 1 2
  2 0 1 2 1
  0 2 1 2 1
  2 2 1 0 1
  1 2 2 0 0
  0 2 1 0 2
  0 2 1 2 0
  2 0 1 2 0

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

  1 0 2 0 2
  2 2 2 1 2
  1 1 0 0 0
  1 1 0 2 1
  2 1 1 1 1
  1 2 2 1 1
  2 1 2 2 1
  2 2 0 1 0
  0 1 2 1 2
  2 2 1 0 0
  1 2 0 2 0
  2 2 2 0 1

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

(The Cake Contest was a special competition for teams, were they should think of the best problem for CEOI competition. Here’s the winning problem:)

N participants of the CEOI should be transported to a national park. They travel in B busses with L seating rows of S seats each, with N<=(B*L*S). The distance between two people sitting next to each other is 1. The distance between people sitting in the same row but not next to each other is 2 and the distance between people sitting M rows apart from each other, but in the same bus, is (M+1). People in different busses always have a distance of 20.

Your goal is to maximise the happiness of the CEOI participants. Each participant has a certain favourite distance to those participants he or she already knows. Participants do not care about distances to people they do not yet know. Global happiness is the sum over all individual happinesses. Individual happiness of a participant is calculated as follows:

An actual distance matching the favourite distance increases the happiness of the participant by 30. The happiness decreases by the difference between actual and favourite distance. If, for example, Alice prefers sitting in a distance of 5 to Bob, while Bob is sitting 3 rows in front of Alice, i.e. at a distance of 4, happiness of Alice will be increased by 29. Note that the favourite distance from Alice to Bob can differ from the favourite distance from Bob to Alice. Since we are at a CEOI, no individual happiness will become less than 0.

Input data

The first line of the input file VOTE4ME.IN contains the positive integers N<=10000, B<=100, L<30 and S <= 10. The following N lines of the input file contain N numbers each. The number I, 0<= I <= 30, in column U and row V is the distance that participant V would like participant U to sit. The favourite distance from a participant to him/herself is always 0; instead of real distances to people he or she does not know, the input file will contain the special value 1.

Output data

The output file VOTE4ME.OUT must consist of N lines, line j, 1<=j<=N containing the happiness of person j in an optimal sitting plan. An optimal sitting plan is one that maximises the global happiness.

Example

VOTE4ME.IN

  4 1 3 2
  0 5 1 2
  1 0 1 1
  2 1 0 6
  3 1 1 0

  25
  29
  26
  30

On the chessboard of size 4x4 there are 8 white and 8 black stones, i.e. one stone on each field. Such a configuration of stones is called a game position. Two stones are adjacent if they are on fields with a common side (i.e. they are adjacent in either horizontal or vertical direction but not diagonal). It means that each stone has at most 4 neighbours. The only legal move in our game is exchanging any two adjacent stones. Your task is to find the shortest sequence of moves transforming a given starting game position into a given final game position.

Input

The starting game position is described in the first 4 lines of input file GAME.IN. There are 4 symbols in each line, which define the colour of each stone in the row from the left to the right. The lines describe the rows of the chessboard from the top to the bottom. Symbol '0' means a white stone and symbol '1' a black one. There is no space symbol separating the symbols in the line. The fifth line is empty. The next 4 following lines describe the final game position in the same way.

Output

The first line of output file GAME.OUT contains the number of the moves. The following lines describe the sequence of moves during the game. One line describes one move and it contains 4 positive integers R₁C₁R₂C₂ separated by single spaces. These are the coordinates of the adjacent fields for the move, i.e. fields , where R₁ (or R₂) is the number of the row and C₁ (or C₂) is the number of the column. The rows on the chessboard are numbe"#008DDC" from 1 (top row) to 4 (bottom row) and the columns are numbe"#008DDC" from 1 (the leftmost column) to 4 (the rightmost one) as well (i.e. the coordinates of the left upper field are ). If there are multiple shortest sequences of moves transforming the starting position to the final position, you can output any one of them.

Example:

GAME.IN

  1111
  0000
  1110
  0010

  1010
  0101
  1010
  0101

Children like playing with blocks (cube wooden bricks). They usually build high towers, but small Johny dreams of different plans. He is going to build a big town. His daddy has bought him a rectangular table; its width is K blocks and its length is L blocks exactly. Johny decided to project a plan of such a town before he starts building the town itself. He has drawn a square-shaped network on the table consisting of KxL squares. He wants to place the towers consisting of one or more blocks on some of the squares of the network drawn; the remaining squares will be empty. Because of the table being so large, Johny is not going to plan exactly for every square how many blocks he will put on it. He only wants to decide about front and right sight shapes of his town. He drew these two views (two-dimensional projections of the planned town) on a paper. You can see an example of these drawings and the adequate town made of wooden bricks in the pictures:

Johny's daddy is afraid they don't have enough blocks to finish building Johny's planned town. You are asked for writing a program to compute the minimal and maximal amount of blocks with which a town corresponding to Johny's plans can be built. Moreover the program can decide about the possibility of building a town satisfying the views.

Input

The first line of input file TOWN.IN contains two positive integers K, L - the width and the length of the table (expressed as numbers of bricks). Neither the width nor the length of the table is greater than 100000 bricks. The following lines of the input file contain the description of the front view of the town. The description consists of a series of heights of visible buildings on each square from the left to the right (the height is measu"#008DDC" by the number of the blocks, too). There is only one number on each line, i.e. the number of the lines with the front view description of the town equals K - the width of the table. Similarly the next L lines of the input file contain the right sight view of the town. The heights of the wooden block towers are now specified from the front line to the back line. You may suppose there is no building in the town with height exceeding 5000 blocks. The maximal number of blocks needed for building the entire town does not exceed 2000000000.

Output

Output file TOWN.OUT contains only one line. If it is not possible to build a town with the front and right sight views given, only a text `No solution.' is written there. In the other case two numbers will be written on the line and separated by a single space. The first one is the minimal and the second one is the maximal amount of blocks small Johny can use to build his town in accordance with his project.

Example 1

TOWN.IN

  4 3
  1
  3
  4
  2
  1
  4
  2

  10 21

Example 2

TOWN.IN

  2 2
  4
  1
  1
  3

  No solution.

Now and then you play the following game with your friend. Your friend writes down a sequence consisting of zeroes and ones. You choose a continuous subsequence (for example the subsequence from the third to the fifth digit inclusively) and ask him, whether this subsequence contains even or odd number of ones. Your friend answers your question and you can ask him about another subsequence and so on. Your task is to guess the entire sequence of numbers.

You suspect some of your friend's answers may not be correct and you want to convict him of falsehood. Thus you have decided to write a program to help you in this matter. The program will receive a series of your questions together with the answers you have received from your friend. The aim of this program is to find the first answer which is provably wrong, i.e. that there exists a sequence satisfying answers to all the previous questions, but no such sequence satisfies this answer.

Input

The first line of input file PARITY.IN contains one number, which is the length of the sequence of zeroes and ones. This length is less or equal to 1000000000. In the second line, there is one positive integer which is the number of questions asked and answers to them. The number of questions and answers is less or equal to 5000. The remaining lines specify questions and answers. Each line contains one question and the answer to this question: two integers (the position of the first and last digit in the chosen subsequence) and one word which is either 'even' or 'odd' (the answer, i.e. the parity of the number of ones in the chosen subsequence, where `even' means an even number of ones and 'odd' means an odd number).

Output

There is only one line in output file PARITY.OUT containing one integer X. Number X says that there exists a sequence of zeroes and ones satisfying first X parity conditions, but there exists none satisfying X+1 conditions. If there exists a sequence of zeroes and ones satisfying all the given conditions, then number X should be the number of all the questions asked.

Example 1

PARITY.IN

  10
  5
  1 2 even
  3 4 odd
  5 6 even
  1 6 even
  7 10 odd

  3

Example 2

PARITY.IN

  10
  5
  1 2 even
  1 4 even
  2 4 odd
  1 10 even
  3 10 even

  5

In the present world you frequently meet a lot of call numbers and they are going to be longer and longer. You need to remember such a kind of numbers. One method how to do it in an easy way is to assign letters to digits as shown in the following picture:

  1 ij    2 abc   3 def
  4 gh    5 kl    6 mn
  7 prs   8 tuv   9 wxy
          0 oqz

Input

The first line of input file PHONE.IN contains the call number, the transcription of which you have to find. The number consists of at most 100 digits. The second line contains the total number of the words in the dictionary (maximum is 50000). Each of the remaining lines contains one word, which consists of maximally 50 small letters of the English alphabet. The total size of the input file doesn't exceed 300KB.

Output

The only line of output file PHONE.OUT contains the shortest sequence of words which has been found by your program. The words are separated by single spaces. If there is no solution to the input data, the line contains text 'No solution.'. If there are more solutions having the minimum number of words, you can choose any single one of them.

Example

There is only one solution to the input file PHONE.IN containing

  7325189087
  5
  it
  your
  reality
  real
  our

  reality our

  4294967296

  No solution.

There is a travel agency in Adelton town on Zanzibar island. It has decided to offer its clients, besides many other attractions, sightseeing the town. To earn as much as possible from this attraction, the agency has accepted a shrewd decision: it is necessary to find the shortest route which begins and ends at the same place. Your task is to write a program which finds such a route.

In the town there are N crossing points numbe"#008DDC" from 1 to N and M two-way roads numbe"#008DDC" from 1 to M. Two crossing points can be connected by multiple roads, but no road connects a crossing point with itself. Each sightseeing route is a sequence of road numbers y₁, ..., y_k, k>2. The road y_i (1<=i<=k-1) connects crossing points x_i and x_i+1, the road y_k connects crossing points x_k and x₁. All the numbers x₁,...,x_k should be different. The length of the sightseeing route is the sum of the lengths of all roads on the sightseeing route, i.e. L(y₁)+L(y₂)+...+L(y_k) where L(y_i) is the length of the road y_i (1<=i<=k). Your program has to find such a sightseeing route, the length of which is minimal, or to specify that it is not possible, because there is no sightseeing route in the town.

Input

The first line of input file TRIP.IN contains two positive integers: the number of crossing points N<=100 and the number of roads M<=10000. Each of the next M lines describes one road. It contains 3 positive integers: the number of its first crossing point, the number of the second one, and the length of the road (a positive integer less than 500).

Output

There is only one line in output file TRIP.OUT. It contains either a string 'No solution.' in case there isn't any sightseeing route, or it contains the numbers of all crossing points on the shortest sightseeing route in the order how to pass them (i.e. the numbers x₁ to x_k from our definition of a sightseeing route), separated by single spaces. If there are multiple sightseeing routes of the minimal length, you can output any one of them.

Example 1

TRIP.IN

  5 7
  1 4 1
  1 3 300
  3 1 10
  1 2 16
  2 3 100
  2 5 15
  5 3 20

  1 3 5 2

Example 2

TRIP.IN

  4 3
  1 2 10
  1 3 20
  1 4 30

  No solution.

The stores manager has sorted all kinds of goods in an alphabetical order of their labels. All the kinds having labels starting with the same letter are sto"#008DDC" in the same warehouse (i.e. in the same building) labelled with this letter. During the day the stores manager receives and books the orders of goods which are to be delive"#008DDC" from the store. Each order requires only one kind of goods. The stores manager processes the requests in the order of their booking.

You know in advance all the orders which will have to be processed by the stores manager today, but you do not know their booking order. Compute all possible ways of the visits of warehouses for the stores manager to settle all the demands piece after piece during the day.

Input

Input file ORDERS.IN contains a single line with all labels of the requested goods (in random order). Each kind of goods is represented by the starting letter of its label. Only small letters of the English alphabet are used. The number of orders doesn't exceed 200.

Output

Output file ORDERS.OUT will contain all possible orderings in which the stores manager may visit his warehouses. Every warehouse is represented by a single small letter of the English alphabet - the starting letter of the label of the goods. Each ordering of warehouses is written in the output file only once on a separate line and all the lines containing orderings have to be sorted in an alphabetical order (see the example). No output will exceed 2 megabytes.

Example

ORDERS.IN

  bbjd

  bbdj
  bbjd
  bdbj
  bdjb
  bjbd
  bjdb
  dbbj
  dbjb
  djbb
  jbbd
  jbdb
  jdbb

All the inhabitants of the planet X build their houses in a triangular shape. In order to save time and effort, they use a special construction method. Everything starts with a straight wall. After that, for the construction of every new house they just add two new walls to an already existing wall, thus resulting in a closed, triangular shaped house. Of course, the two new added walls might also be used as starting walls for new houses. Sometimes, using this construction pattern, they arrive at situations where some houses are completely enclosed in others (like in the figure). However, this is not a problem, because kids might live in the included houses.

To light up their houses, the X-habitants install a light bulb on every corner of the final construction (a bulb in a corner is common to all the houses sharing that corner). On each corner, there is a switch whose touch toggles the state (on/off) of the bulb from both that corner and also that of all the bulbs of the connected corners. Two corners are conside"#008DDC" connected if they are placed at the end of the same wall.

Write a program that finds a switch touch sequence that will turn on all the light bulbs, starting from a given state.

Input

File name: X.IN
Line 1: N (an integer, the number of corners of the building, labelled from 1 to N);
Lines 2..2xN-2: I J (two integers, separated by a blank, representing a wall between the corners I and J);
Line 2xN-1: S₁ S₂ ... S_N (N integers (separated by blanks) whose values are 0's or 1's, corresponding to the state of the N light bulbs; 0 means off; 1 means on). The input data are guaranteed to represent a building that can be constructed in the specified pattern.

Output

File name: X.OUT
Line 1: L₁ L₂ ... L_K (K integers, separated by blanks, represen-ting the list of the labels of the switches to be touched. If there are several solutions, only one is requi"#008DDC". If there is no possible solution, you should write in the output file a single line containing the number 0.)
Limits 3<=N<=1000

Example

X.IN

  6
  1 3
  1 4
  1 5
  2 3
  2 4
  3 4
  3 6
  4 5
  4 6
  0 1 1 1 0 0

  1 6

The Romanian Ministry of Transport decides to upgrade the Romanian roads. Each road is bidirectional and directly connects two towns. No two towns are directly connected by more than one road. The existing road network ensures direct or indirect links between any two towns in Romania.

However, upgrading the roads implies closing, in turn, each road and performing the necessary repairs. During these operations, it is necessary to preserve the road network connectivity. In order to do so, the Minister decides that new roads should be built, so that no matter which single road is closed at any given moment (exactly one road at a time), the traffic between any given pair of towns should still be possible. Of course, the number of these newly added roads should be minimized. Furthermore, no new road may directly connect two directly connected towns.

Write a program that determines the minimum number of the additional roads to be built and the pairs of towns to be connected with them. If there are several optimal solutions, only one is requi"#008DDC".

Input

File name: ROADS.IN
Line 1: N M (Two integers, separated by a blank, representing respectively the number of the towns and the number of the roads. The towns are labelled from 1 to N.)
Lines 2..M+1: T1 T2 (Two integers separated by a blank, representing the two towns connected by a road.)

Output

File name: ROADS.OUT
Line 1: K (an integer, representing the minimum number of additional roads)
Lines 2..K+1: C1 C2 (two integers separated by a blank, representing a pair of towns (cities) to be connected by a road)

Remark

The order of town pairs in the output file is irrelevant.
Limits 3<=N<=2500 2<=M<=20000

Example

ROADS.IN

  4 3
  1 2
  2 3
  2 4

  2
  1 4
  1 3

Definition:
A caterpillar is a particular kind of tree with the following property: there is a central chain such that each of the tree's nodes lie either on the central chain, or they are adjacent to that chain. Below there are shown two caterpillars. The darkened nodes indicate the chain.

The chain is not necessarily unique. For example, another possible chain for the second caterpillar is 3-2-5-9.

Given a caterpillar with N nodes, write a program which labels the nodes with numbers from 1 to N such that: each label from 1 to N is used exactly once and no two edges in the tree have the same absolute value of the difference between the labels of their adjacent nodes.

For the second caterpillar above, a possible labeling is indicated below along with the corresponding differences on the edges:

Input

File name: CP.IN
Line 1: N (one integer, the number of nodes) Lines 2..N: X Y (two integers, separated by a blank, which are two adjacent nodes connected by an edge)
The input data is correct, and the input tree is a caterpillar.

Output

File name: CP.OUT
Line 1: L₁ L₂ ... L_N (N integers, separated by blanks, where L_i represents the label associated with the node i)
If there are multiple solutions, only one is requi"#008DDC". If no labeling is possible, the output file should contain only one line with the word: IMPOSSIBLE

Limits

2<=N<=10000

Example

The following input (CP.IN) describes the caterpillar from the Figure 2 and the output (CP.OUT) the labeling from the Figure 3.

CP.IN

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

  8 1 5 2 9 4 6 3 7

Consider a game based on the device shown in the image below:

From a given position, a ball is released in free fall at moment 0. The ball falls at a constant speed of 1 meter per second. When the ball reaches a platform it starts rolling towards one or the other of its edges, at the choice of the player, at the same speed of one meter per second. When it reaches the edge of the platform, it continues its vertical free fall. The ball is not allowed to free fall for more then MAX meters at one time (between two platforms).

Write a program that finds a way to roll the ball on the platforms so that it reaches the floor as soon as possible without breaking.

Input

File name: FALL.IN
Line 1: N X Y MAX (four integers, separated by a space: the number of platforms (excluding the floor), the starting position of the ball (horizontal and vertical coordinates), and the maximum allowed free fall distance; the platforms are numbe"#008DDC" from 1 through N)
Lines 2..N+1: X1_i X2_i H_i (three integers, separated by spaces; the i-th platform is situated at height H_i, between horizontal coordinates X1_i and X2_i inclusive (X1_i<X2_i, i=1..N).

Remarks

  3 8 17 20
  0 10 8
  0 10 13
  4 14 3

  23
  2 4 1
  1 11 1
  3 16 1

C/C++: sticks.h header
with the following routines:

procedure putMove(nr,label1,label2:Integer); (Pascal)
void putMove(int nr, int label1, int label2); (C/C++)
called to announce your program's move, that is, "eliminate from row nr the sticks labeled with numbers from label1 to label2 inclusively"

getMove(var nr,label1,label2:Integer); (Pascal)
void getMove(int *nr, int *label1, int *label2); (C/C++)
called to obtain your opponent's move, in the same format as above; (C/C++ only: pass pointers to the variables in which you want to obtain the data)

Your program should alternately call these two routines until there are no more sticks on the table. Our module will terminate the game if your program makes an invalid move (of course you will get no points in this case).

Example

STICKS.IN

  2
  1 3
  1

possible call succession in PASCAL

  getMove(nr, k1, k2); -> nr=2, k1=2, k2=2
  putMove(1, 1, 1);
  getMove(nr, k1, k2); -> nr=2, k1=1, k2=1
  putMove(2, 3, 3);
  **** your program wins ****

You can copy from here a demo version of the Unit, but you must keep in mind that this is only a demo version, and it will not play at it's best:

---

sticks.pas (Pascal)

---

  {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+,Y+}
  {$M 16384,0,655360}
  unit sticks;

  interface

  procedure putMove(nr,label1,label2:integer);
  procedure getMove(var nr,label1,label2:integer);

  implementation

  const vturn:integer=2;

  var vx,vy,vi,vj,vk,vl,vm,vn:longint;
    vfi:text;
    vst:arrayof integer;
    vpp:arrayof integer;
    vxxx,vyyy,vzzz:integer;

  procedure readdata;
    begin
    assign(vfi,'sticks.in');
    reset(vfi);
    readln(vfi,vn);
    for vi:=1 to vn do
      read(vfi,vst);
    readln(vfi);
    readln(vfi,vturn);
    close(vfi);
    for vi:=1 to vn do
      for vj:=1 to vst do
        vpp:=1;
    end;

  function empty:boolean;
    begin
    empty:=false;
    for vi:=1 to vn do
      for vj:=1 to vst do
        if vpp=1 then exit;
    empty:=true;
    end;

  procedure eroare(s:string);
    begin
    writeln(s);
    halt;
    end;

  procedure putMove(nr,label1,label2:integer);
    var vmm,vnn:integer;
    begin
    if vturn=2 then
      begin
      readdata;
      if vturn=1 then
        eroare('Wrong player started the game');
      end;
    if vturn=1 then
      eroare('The other player''s turn');
    vturn:=1-vturn;
    if (nr<1)or(nr>vn) then
      eroare('Invalid move');
    if (label1>label2)or(label2<1)or(label1>vst) then
      eroare('Invalid move');
    if label2-label1>2 then
      eroare('Invalid move');
    for vi:=label1 to label2 do
      if vpp=0 then
        eroare('Invalid move');
    for vi:=label1 to label2 do
      vpp:=0;
    vnn:=label2-label1+1;
    vm:=0;
    vi:=label1;
    while vpp=1 do
      begin
      dec(vi);
      inc(vm);
      inc(vnn);
      end;
    vm:=0;
    vi:=label2;
    while vpp=1 do
      begin
      inc(vi);
      inc(vm);
      inc(vnn);
      end;
    if empty then
      begin
      halt;
      end;
  end;

  procedure getMove(var nr,label1,label2:integer);
    var vm:integer;
    begin
    if vturn=2 then
      begin
      readdata;
      if vturn=0 then
        eroare('Wrong player started the game');
      end;
    if vturn=0 then
      eroare('The other player''s turn');
    vturn:=1-vturn;
    for vk:=1 to 100 do
      begin
      vi:=random(vn)+1;
      vj:=random(vst)+1;
      if vpp=1 then
        begin
        vm:=0;
        vk:=0;
        while vpp=1 do
          begin
          inc(vk);
          inc(vm);
          end;
        vk:=0;
        while vpp=1 do
          begin
          inc(vk);
          inc(vm);
          end;
        vk:=vm;
        dec(vk);
        vpp:=0;
        nr:=vi;
        label1:=vj;
        label2:=vj;
        exit;
        end;
      end;
    for vi:=1 to vn do
      for vj:=1 to vst do
        if vpp=1 then
          begin
          vk:=0;
          while vpp=1 do inc(vk);
          vpp:=0;
          nr:=vi;
          label1:=vj;
          label2:=vj;
          exit;
          end;
    end;

  end.

---

sticks.h (C/C++)

---

  #include <stdio.h>
  #include <stdlib.h>

  int va1_turn=2;
  long va1_n;
  int va1_st;
  int va1_pp;

  void va1_readdata(void)
  {
    int i, j;
    FILE *fi=fopen("sticks.in", "r");

    fscanf(fi, "%d", &va1_n);
    for (i=1; i<=va1_n; fscanf(fi, "%d", va1_st+(i++)));
    fscanf(fi, "%d", &va1_turn);
    fclose(fi);

    for (i=1; i<=va1_n; i++)
      for (j=1; j<=va1_st=1);
  }

  int va1_empty(void)
  {
    int i, j;

    for (i=1; i<=va1_n; i++)
      for (j=1; j<=va1_st; j++)
        if (va1_pp==1) return 0;
    return 1;
  }

  void va1_eroare(char *s)
  {
    puts(s);
    exit(1);
  }

  void putMove(int nr, int label1, int label2)
  {
    int mm, nn, i, m;

    if (va1_turn==2)
    {
      va1_readdata();
      if (va1_turn==1) va1_eroare("Wrong player started the game");
    }
    if (va1_turn==1)
      va1_eroare("The other player's turn");
    va1_turn=1-va1_turn;

    if (nr<1 || nr>va1_n)
      va1_eroare("Invalid move");
    if (label1>label2 || label2<1 || label1>va1_st)
      va1_eroare("Invalid move");
    if (label2-label1>2)
      va1_eroare("Invalid move");
    for (i=label1; i<=label2; i++)
      if (!va1_pp) va1_eroare("Invalid move");

    for (i=label1; i<=label2; i++)
      va1_pp=0;

    nn=label2-label1+1;
    m=0;
    i=label1;
    while (va1_pp==1)
    {
      i--; m++; nn++;
    }

    m=0;
    i=label2;
    while (va1_pp==1)
    {
      i++; m++; nn++;
    }

    if (va1_empty())
    {
      exit(0);
    }
  }

  void getMove(int *nr, int *label1, int *label2)
  {
    int m, i, j, k, xxx, yyy, zzz;

    if (va1_turn==2)
    {
      va1_readdata();
      if (!va1_turn) va1_eroare("Wrong player started the game");
    }
    if (!va1_turn)
      va1_eroare("The other player's turn");
    va1_turn=1-va1_turn;

    for (k=1; k<=100; k++)
    {
      i=rand()%va1_n+1;
      j=random(va1_st)+1;
      if (va1_pp==1)
      {
        m=k=0;
        while (va1_pp==1)
        { k++; m++; }
        k=0;
        while (va1_pp==1)
        { k++; m++; }
        k=m-1;
        va1_pp=0;
        *nr=i;
        *label1=j;
        *label2=j;
        return;
      }
    }

    for (i=1; i<=va1_n; i++)
      for (j=1; j<=va1_st; j++)
        if (va1_pp==1)
        {
          k=0;
          while (va1_pp==1) k++;
          va1_pp=0;

          *nr=i;
          *label1=j;
          *label2=j;
          return;
        }
  }

---

Enlightened landscape

Consider a landscape composed of connected line segments:

Above the landscape, N light bulbs are hang at the same height T in various horizontal positions. The purpose of these light bulbs is to light up the entire landscape. A landscape point is conside"#008DDC" lit if it can "see" a light bulb directly, that is, if the line segment which links the point with a bulb does not contain any other landscape segments point.

Write a program that determines the minimum number of light bulbs that must be switched on in order to illuminate the entire landscape.

Input

Input file name: LIGHT.IN
Line 1: M (an integer, the number of landscape height specifications, including the first and the last point of the landscape)
Lines 2..M+1: X_i H_i (two integers, separated by a space: the landscape height H_i at horizontal position X_i, 1<=i<=M; for 1<=i<=M-1 we have X_i+1>X_i; any two consecutive specified points identify a segment of line in the landscape)
Line M+2: N T (two integers, separated by a space, the number of light bulbs and their height coordinate (altitude); the bulbs are numbe"#008DDC" from 1 to N)
Line M+3: B₁ B₂ ... B_N (N integers, separated by spaces: the horizontal coordinates of the light bulbs B_i+1>B_i, 1<=i<=N-1)

Output

File name: LIGHT.OUT Line 1: K (an integer: the minimum number of light bulbs to be switched on)
Line 2: L₁ L₂ ... L_K (K integers, separated by spaces: the labels of the light bulbs to be switched on spe-cified in increasing order of their horizontal coordinates)

Limits

1<=M<=200
1<=N<=200
1<=X_i<=10000 for 1<=i<=M
1<T<=10000
1<=H_i<=10000 for 1<=i<=M
T>H_i for any 1<=i<=M
X₁<=B₁ and B_N<=X_M
The task always has a solution for the test data. If there are multiple solutions, only one is requi"#008DDC".

Example

LIGHT.IN

  6
  1 1
  3 3
  4 1
  7 1
  8 3
  11 1
  4 5
  1 5 6 10

LIGHT.OUT

  2
  1 4

---

2001
(Zalaegerszeg, Hungary) Day 1: Chain of Atoms | Printed Circuit | Round Trip
Day 2: Components of a Bitmap | Wildcard Patterns | Selecting a Majority Member

---

Chain of Atoms

Scientists are investigating a special kind of molecule. It is known that the molecule consists of N different atoms, labeled from 1 to N, and the structure of the molecule is a linear chain. The scientists are equipped with a distance meter. At one time, this instrument can measure the distance between any two atoms in the molecule. The distance, reported by the instrument, is the absolute value of the difference of the two atom positions in the chain. If you access no atom for more than three times no damage is done to the molecule. If you access one or more atoms four times the molecule gets damaged. If you access one or more atoms five times the molecule gets destroyed.

You are to write a program that discovers the complete structure of the molecule by determining the sequence of the atoms in the molecule.

To operate the distance meter, you are given a library meter with three operations:

• Size, to be called once at the beginning, without arguments; it returns the value of N. Size must be called before any call to Span.
• Span, to be called with two atom labels as arguments; it returns the distance between the atoms.
• Answer, to be called at the end, must be used to submit your solution. Answer has two integer arguments, i and x, and it tells that the label of the atom at position i in the molecule is x. For each i (1<=i<=N), Answer must be called exactly once in ascending order of i. There are always two symmetric solutions, and you can submit any one of them.

The dialogue between your program and the library procedures is logged in the text file chain.out. This log file also contains your answer and the error message in case of an error.

Instruction for Pascal programmers:
Include the import statement uses meter; in the source code.

Instructions for C/C++ programmers:
Use the instruction #include "meter.h" in the source code, create a project file chain.gpr in the task directory, add the files chain.c (chain.cpp) and meter.o into this project, and then compile and/or make your program.

Experimentation

You can experiment with the library by creating a text file chain.in. The file must contain two lines. The first line should contain the integer N, the number of atoms. The second line should contain a test case: a sequence of the atom labels, consisting of N different integers between 1 and N.

Example for experimentation

chain.in

  5
  1 3 5 2 4

chain.out

  Size=5
  Span(1,2)=3
  Span(1,3)=1
  Span(2,3)=2
  Span(4,5)=2
  Span(1,4)=4
  Span(3,5)=1
  Your Answer:
  1 3 5 2 4
  Max. Access/Atom:
  3

Constraints

C/C++ function declarations: int Size(void);, int Span(int x, int y);, void Answer(int i, int x);.

---

Printed Circuit

A printed circuit is a board that consists of nodes and wire segments connecting pairs of nodes. We consider a special kind of printed circuits where the nodes are arranged in a rectangular grid, and the wire segments connect (vertically or horizontally) adjacent nodes only. A printed circuit is called connected if any two distinct nodes are connected with a series of wire segments. Given is a printed circuit where wire segments already connect several adjacent nodes. We have to add new wire segments in order to make the printed circuit connected. The cost of a new wire segment is 1 if it is vertical and 2 if it is horizontal in the grid.

You are to write a program that computes a least cost completion of a given circuit. Your program should solve the following three subtasks:

1. Determine the number of new wire segments of a least cost completion.
2. Compute the value of the least cost.
3. Produce a list of wire segments of a least cost completion.

Input

The first line of the file circuit.in contains two integers, N and M. N (1<=N<=100) is the number of rows and M (1<=M<=100) is the number of columns in the grid. The nodes of the circuit are identified by their coordinates; the node in the upper left corner is at (1,1), and the node in the lower right corner is at (N, M). Each of the next N lines contains M integers. The number in row i and column j of these lines describes the wire segments between the pair of nodes (i,j) and (i+1,j), and also between the pair of nodes (i,j) and (i,j+1) in the following way.

0 means that neither the pair of nodes (i,j) and (i+1,j) nor the pair of nodes (i,j) and (i,j+1) are connected by wire segments.
1 means that only the pair of nodes (i,j) and (i+1,j) is connected by a wire segment.
2 means that only the pair of nodes (i,j) and (i,j+1) is connected by a wire segment.
3 means that both the pair of nodes (i,j) and (i+1,j), and the pair of nodes (i,j) and (i,j+1) are connected by wire segments.

Note that not all 4 values are valid at certain positions (e.g. at position (N,M) only value 0 is valid).

Output

The first line of the file circuit.out should contain two integers, K and V. The integer K is the number of new wire segments of a least cost completion; and the integer V is the value of the least cost. The rest of the file must contain K lines; the list of wire segments of a least cost completion (in arbitrary order). Each line must contain three numbers describing exactly one new wire segment: i, j and d, where (i,j) are the coordinates of a node, and d is either 1 or 2. 1 means that the new wire segment connects the nodes (i,j) and (i+1,j), and 2 means that the new wire segment connects the nodes (i,j) and (i,j+1)

Example

The example input file corresponds to the circuit in 1st figure. The example output file is a possible least cost completion, and is depicted in Figure 2. circuit.in

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

circuit.out

  5 6
  1 1 1
  3 2 1
  3 3 1
  3 3 2
  2 5 1

---

Round Trip

Your team decided to take a round trip in the host country after the competition. You want to travel to a destination city and return to the starting city. The only requirement your team specified is that the forward route to the destination city and the return route back to the starting city must contain the least possible number of common roads. (A route can not contain any road twice or more times.)

You are to write a program that computes two routes between the starting city and the destination city so that the number of common roads in the two routes is as small as possible.

Input

The first line of the file trip.in contains two integers, S and D (S<>D), the labels of the starting and the destination cities, respectively. The second line contains two integers, N and M, where N (3<=N<=1000) is the number of the cities and M (2<=M<=100000) is the number of the roads between the cities. The cities are labeled from 1 to N. Each of the next M lines in the file contains two integers, P and Q (1<=P,Q<=N, P<>Q), meaning that there is a two-way road between city P and city Q. There is at most one road between any two cities.

Output

The first line of the file trip.out must contain one integer, the least possible number of common roads of the forward and the return routes. The second line should contain a forward route as a sequence of city labels, including the starting and ending city. The third line should contain a return route as a sequence of city labels (again including the starting and ending cities). If there are more possible pairs of routes with the same least number of common roads then your program may output any one of them. If there is no route from the starting city to the destination city then the first and only line must contain -1.

Example input and output

trip.in

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

trip.out

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

---

Components of a Bitmap

Black and white pictures are usually sto"#008DDC" as bitmaps. A bitmap is a rectangular grid of pixels.

A polyline between pixels P and Q is a sequence of black pixels P=P₁, P₂, ..., P_k=Q, where P_i and P_i+1 (i=1, ..., k-1) are (vertically or horizontally) adjacent pixels. A polyline P₁, P₂, ..., P_k is closed if P₁=P_k, and P_i<>P_j (i=1,...,k-1, j=2,...,k) for i<j unless i=1 and j=k (that is the polyline does not contain the same pixel twice).

A set of black pixels S is connected if for each pair of pixels (P,Q) in S there is at least one polyline L between P and Q with all pixels of L belonging to S.

A component of a bitmap is a maximal connected set of black pixels. A component may enclose holes. A hole consists of white pixels that are inside a closed polyline. A compact component encloses no holes.

Note that in Figure 1 the white pixel in the middle, marked with x, is not inside the highlighted closed polyline.

Figure 2 shows a bitmap with five components, of which two are compact ones.

You are to write a program that computes the total number of components and the number of compact components of a given coded bitmap.

The bitmaps under investigation are coded (compressed) with the following method. Each row is coded with a sequence of integers W₁, B₁, ..., W_k, B_k, where W_i is the number of consecutive white pixels, and B_i is the number of consecutive black pixels, respectively.

For example, the code of the first line of the bitmap in Figure 2 is the sequence 4 7 4 4 1 0. Components 4 and 5 are compact, while components 1, 2 and 3 are not compact.

Input

The first line of the file bitmap.in contains two positive integers, N and M. N (2<=N<=10000) is the number of rows and M (2<=M<=1000) is the number of columns of the bitmap. The next N lines contain the coded bitmap according to the paragraph on encoding. Each line terminates with -1.

Output

The file bitmap.out must contain two lines, with a single integer in each line. The first line contains the number of all components and the second line contains the number of compact components of the input bitmap.

Example

bitmap.in

  10 20
  4 7 4 4 1 0 -1
  0 4 1 4 1 4 1 1 1 3 -1
  1 3 4 6 2 4 -1
  0 7 9 4 -1
  0 1 4 9 1 1 4 0 -1
  0 1 1 3 1 8 1 5 -1
  0 1 1 1 1 1 1 8 1 1 3 1 -1
  0 1 1 3 1 1 3 1 2 1 1 1 3 1 -1
  0 1 5 1 1 6 1 1 3 1 -1
  0 7 3 4 1 1 3 1 -1

bitmap.out

  5
  2

---

Wildcard Patterns

Wildcard patterns are frequently used to specify sets of names. For example, we can specify all file names which start with h and end with bak by the pattern h*bak.

A wildcard pattern is a string that may contain * characters as wildcards. A string W matches a pattern P if W can be obtained from P by substituting some (possibly empty) string for each * character in P. (Different strings may be substituted for different occurrences of *.) For a pair of patterns P₁ and P₂, Q is a common pattern of P₁ and P₂ if any string that matches Q also matches both P₁ and P₂.

A set Q₁, Q₂, ..., Q_L of common patterns is called complete if any string that matches both P₁ and P₂ matches at least one Q_i (1<=i<=L).

You are to write a program that for a given pair of patterns P₁ and P₂ computes

1. at least one common pattern (but no wrong patterns),
2. or a complete set of common patterns with no more than 6666 entry,
3. or a complete set of common patterns which is minimal in the number of elements (i.e. there is no smaller set of common patterns, which is complete).

Input

The first and the second lines of the file pattern.in contain the patterns P₁ and P₂. The patterns are composed of the lowercase letters from 'a' to 'z' and the '*' character. Each pattern contains no more than 20 characters. The number of the * characters in each pattern is between 0 and 6.

Output

The first line of the file pattern.out must contain the integer K, the number of common patterns computed as a solution. The next K lines contain one common pattern in each line; these constitute the solution. The order of the common patterns is irrelevant. Both case B and C can be solved within the specified limit of 6666 entries. If there is no common pattern of P₁ and P₂, then the first and only line must contain the number 0.

Example input and output

pattern.in

  *ab*
  ba*b

pattern.out for case C

  4
  ba*ab*b
  bab*b
  ba*ab
  bab

---

Selecting a Majority Member

Students in your school belong to two disjoint groups. It is known that one group, called the majority group, contains more students than the other group. We want to select a student who belongs to the majority group. Student's identifiers are integers from 1 to the number of students. The only operation that we can perform is to query whether two students belong to the same group.

You are to write a program that finds a student who belongs to the majority group, while it performs as few queries as possible.

To perform queries, you are given a library query with three operations:

• Size, to be called once at the beginning, without arguments; it returns N, the number of all students. Size must be called before the first call to Member.
• Member, to be called with two student identifiers as arguments; it returns 1 if these two students belong to the same group, otherwise it returns 0.
• Answer, to be called once at the end, must be used to submit your solution. Answer has an integer argument, the label of a student belonging to the majority group.

The dialogue between your program and the library procedures is logged in the text file select.out. This log file also contains your answer and an indication whether your answer was correct.

Your answer is accepted only if for any two disjoint groups of all students A and B, for which all your queries give the same result, your answer identifies a member of the largest group of A and B. The library forces your program to issue all the queries that are necessary to identify a member of the majority group. That is, there are no pre-defined test cases but the library produces them "on the fly".

Instruction for Pascal programmers:
Include the import statement uses query; in the source code.

Instructions for C/C++ programmers:
Use the instruction #include "query.h" in the source code, create a project file select.gpr in the task directory, add the files select.c (select.cpp) and select.o into this project, and then compile and/or make your program.

Experimentation

You can experiment with the library by creating a text file select.in. The first and only line must contain the integer N, the number of all students. N must be an odd number!

Example for experimentation

select.in

  7

select.out

  Size=7
  Member(1,2)=0
  Member(3,4)=1
  Member(5,6)=1
  Member(4,6)=0
  Your Answer: 7, Correct
  Majority Group:
  2 5..7
  Non-majority Group:
  1 3 4
  Number of Queries: 4
  Full Possible Score: 3
  Your Score: 3

Constraints

C/C++ function declarations: int Size(void);, int Member(int x, int y);, void Answer(int x);.

---

2002
(Košice, Slovakia) Day 1: Bugs Integrated, Inc. | Conqueror's battalion | A decorative fence
Day 2: A highway and the seven dwarfs | Royal guards | Birthday party

---

Bugs Integrated, Inc.

Bugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six terabyte Q-RAM chip. Each chip consists of six unit squares arranged in a form of a 2×3 rectangle. The way Q-RAM chips are made is such that one takes a rectangular plate of silicon divided into N×M unit squares. Then all squares are tested carefully and the bad ones are marked with a black marker.

Finally, the plate of silicon is cut into memory chips. Each chip consists of 2×3 (or 3×2) unit squares. Of course, no chip can contain any bad (marked) squares. It might not be possible to cut the plate so that every good unit square is a part of some memory chip. The corporation wants to waste as little good squares as possible. Therefore they would like to know how to cut the plate to make the maximum number of chips possible.

Task

You are given the dimensions of several silicon plates and a list of all bad unit squares for each plate. Your task is to write a program that computes for each plate the maximum number of chips that can be cut out of the plate.

Input description

The first line of the input file consists of a single integer D (1<=D<=5), denoting the number of silicon plates. D blocks follow, each describing one silicon plate. The first line of each block contains three integers N (1<=N<=150), M (1<=M<=10), K (0<=K<=MN) separated by single spaces. N is the length of the plate, M is its height and K is the number of bad squares in the plate. The following K lines contain a list of bad squares. Each line consists of two integers x and y (1<=x<=N, 1<=y<=M) - coordinates of one bad square (the upper left square has coordinates ).

Output description

For each plate in the input file output a single line containing the maximum number of memory chips that can be cut out of the plate.

Example input

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

Example output

  3
  4

---

Conqueror's battalion

In the whole history of mankind one can find several curious battles, like the following one in France, in 1747...

There was a fortress in Bassignac-le-Haut, a small village lying on the left bank of river Dordogne, just over the Chastang dam. From the dam up to the fortress there was a wide staircase made out of "#008DDC" marble. One day in the morning, the guard spotted a large battalion approaching the fortress, with a dreaded leader - The Conqueror.

When The Conqueror reached the fortress, he was already awaited by its commandant. As the commandant had only a small part of his soldiery available, he proposed to The Conqueror: "I see that you have many soldiers behind you, standing on the stairs. We can play a small 'game': In each round, you will divide your soldiers into two groups in an arbitrary way. Then I will decide which one of them stays and which one goes home. Each soldier that stays will then move up one stair. If at least one of your soldiers reaches the uppermost stair, you will be the winner, in the other case, you will be the loser. And your destination will be the dam down there...", added the commandant, pointing to the Chastang dam by his hand.

The Conqueror immediately liked this game, so he agreed and started to 'conquer'.

Task

Your role is The Conqueror's now. There are N stairs to the fortress (2<=N<=2000) and you have at most 1 000 000 000 soldiers. For each stair, you are given the number of soldiers standing on it, with number 1 being the uppermost stair and N the bottom one. None of your soldiers stands on stair 1 at the beginning.

For each starting position given to your program, if the position is winning (i.e. there is a strategy that enables you to win the game regardless of your opponent's moves), your program should win. Otherwise it should just play the game (and lose) correctly.

This is an interactive problem; you will play against a library as specified below. In each round, your program will describe a group of soldiers to our library. The library returns 1 or 2 specifying which group of soldiers should stay (1 means the group you described, 2 means the rest of the soldiers). In case the game ends (either because you won or there are no more soldiers in the game), the library will terminate your program correctly. Your program may not terminate in any other way.

Library interface

The library libconq provides two routines:

• start - returns the number N and fills an array stairs with numbers of soldiers standing on the stairs (i.e. there are stairs soldiers standing on stair i)
• step - takes an array subset (with at least N elements), describing the group of soldiers you chose, and returns 1 or 2 as described above; the group of soldiers is specified by numbers of soldiers on each stair, as in the start function

If you fail to specify a valid group of soldiers, the game will be terminated and your program will score zero points for the particular test case. Please note that also in C/C++ the stairs are numbe"#008DDC" starting from 1.

Following are the declarations of these routines in FreePascal and C/C++:

  procedure start(var N: longint; var stairs:array of longint);
  function step(subset:array of longint): longint;
  void start(int *N, int *stairs);
  int step(int *subset);

Below you can find examples of library usage in both FreePascal and C/C++; both fragments do the same - start the game and then play one round, with the chosen group containing all soldiers on randomly chosen stairs. Your real program will probably play the rounds in an infinite loop.

You are strongly encouraged to define the arrays stairs and subset in the same way as they are defined in the example below. (Note that the FreePascal library returns its answer in the first N elements of the array regardless of how you defined it, the C/C++ library returns its answer in the elements with indices 1 to N.)

FreePascal example

  uses libconq;
  var stairs: array of longint;
  subset: array of longint;
  i,N,result: longint;
  ...
  start(N,stairs);
  ...
  for i:=1 to N do
    if random(2)=0 then
      subset:=0
    else
      subset;
  result:=step(subset);
  ...

C/C++ example

  #include "libconq.h"
  int stairs;
  int subset;
  int i,N,result;
  ...
  start(&N, stairs);
  ...
  for (i=1;i<=N;i++)
    if (rand()%2==0)
      subset=0;
    else
      subset;
  result=step(subset);
  ...

You have to link the library to your program - by uses libconq; in FreePascal and by #include "libconq.h" in C/C++, where you have to compile your program by adding libconq.c to the compiler arguments.

An example of the game

You	Library
start(N,stairs)	N=8, stairs=(0,1,1,0,3,3,4,0)
step((0,1,0,0,1,0,1,0))	returns 2
step((0,1,0,0,0,1,0,0))	returns 2
step((0,0,0,3,2,0,0,0))	returns 1
step((0,0,2,0,0,0,0,0))	returns 2
step((0,1,0,0,0,0,0,0))	returns 2
step((0,1,0,0,0,0,0,0))	no return: you won

Resources

On the web page you may find example libraries for both C/C++ and FreePascal. These libraries are different from those that will be used during testing. You may use them to make sure your library calls are correct. The example library reads the input from the file libconq.dat, containing two lines. On the first line is the number N of stairs, the second line contains N integers - the numbers of soldiers on each of the stairs 1..N.

The file libconq.dat for the example above would look like this:

  8
  0 1 1 0 3 3 4 0

---

libconq.pas (Pascal)

---

  unit libconq;

  interface

  const
    MAX_N = 2000;
    MAX_M = 1000000000;

  procedure start(var N: longint; var stairs: array of longint);
  function step(subset: array of longint): longint;

  implementation

  const
    game_N: longint = 0;
    lib_usage: longint = 0;

  var
    st: array of longint;
    lib_txt: string;

  procedure lib_error(code: longint; s: string);
    var
      f: text;
    begin
    assign(f,'libconq.out');
    rewrite(f);
    writeln(f,s);
    close(f);
    halt(code);
    end;

  function int2str(i:longint): string;
    var
      s:string;
    begin
    str(i,s);
    int2str:=s;
    end;

  procedure start(var N: longint; var stairs: array of longint);
    var
      f: text;
      i: longint;
    begin
    if (lib_usage<>0) then
      lib_error(1,'start() called too many times');
    inc(lib_usage);
    assign(f,'libconq.dat');
    {$I-}
    reset(f);
    {$I+}
    if IOResult<>0 then
      begin
      randomize;
      N:=2+random(MAX_N-2);
      stairs:=0;
      for i:=1 to N-1 do stairs:=random(i*i);
      end
    else
      begin
      read(f,N);
      for i:=0 to N-1 do read(f,stairs);
      close(f);
      end;
    game_N:=N;
    for i:=1 to N do st;
  end;

  function decide(a: array of longint): longint;
    begin
    decide:=1+random(2);
    end;

  function step(subset: array of longint): longint;
    var
      choice,i,wrong,cnt: longint;
    begin
    if (lib_usage=0) then
      lib_error(1,'call start() first!');
    inc(lib_usage);
    { check if a is a valid subset }
    wrong:=0;
    for i:=1 to game_N do
      begin
      if ((subset)) then
        wrong:=i;
      if (wrong<>0) then
        break;
      end;
    if (wrong<>0) then
      begin
      lib_txt:='wrong number of soldiers on stair '+int2str(wrong)+
        ': '+int2str(subset)+
        ' requested, '+int2str(st)+
        ' available';
      lib_error(1,lib_txt);
      end;
    { decide }
    choice:=decide(subset);
    { choice 1: move subset one stair up, discard the rest }
    if (choice=1) then
      begin
      for i:=1 to game_N do st;
      for i:=1 to game_N do st;
      end
    else  { choice 2: discard subset, move complement one stair up }
      begin
      for i:=1 to game_N do dec(st);
      for i:=1 to game_N do st;
      end;
    { check if there are any soldiers left }
    { check if there is any soldier at position 1 }
    cnt:=0;
    for i:=1 to game_N do if st<>0 then inc(cnt);
    if (cnt=0) then
      begin
      lib_txt:='You lost!';
      lib_error(0,lib_txt);
      end;
    if (st<>0) then
      begin
      lib_txt:='You won!';
      lib_error(0,lib_txt);
      end;
    step:=choice;
    end;

  end.

---

libconq.h (C/C++)

---

  #ifndef __LIBCONQ_H
  #define __LIBCONQ_H

  #define MAX_N 2000
  #define MAX_M 1000000000

  void start(int *N, int *stairs);
  int step(int *subset);

  #endif /* __LIBCONQ_H */

---

libconq.c (C/C++)

---

  #include 
  #include 
  #include 
  #include 
  #include "libconq.h"

  static int game_N=0;
  static int st;

  static int lib_usage = 0;
  static char lib_txt;

  static void lib_error(int code, char *s)
  {
    FILE *f;
    f=fopen("libconq.out","w");
    fprintf(f,"%s\n",s);
    fclose(f);
    exit(code);
  }

  void start(int *N, int *stairs)
  {
    FILE *f;
    int i;

    if (lib_usage!=0)
      lib_error(1,"start() called too many times");
    lib_usage++;

    if ((f=fopen("libconq.dat","r"))==NULL)
    {
      srand(time(NULL));
      (*N)=2 + rand()%(MAX_N-2);
      stairs=0;
      for (i=2;i<=(*N);i++) stairs=rand()%(i*i);
    }
    else
    {
      fscanf(f,"%d ",N);
      for (i=1;i<=(*N);i++) fscanf(f,"%d ",&stairs);
      fclose(f);
    }

    game_N=(*N);
    for (i=1;i<=(*N);i++) st;
  }

  static int decide(int *a)
  {
    return (1+rand()%2);
  }

  int step(int *subset)
  {
    int choice,i,wrong,cnt;

    if (lib_usage==0) lib_error(1,"call start() first!");
    lib_usage++;

    /* check if a is a valid subset */
    wrong=0;
    for (i=1;i<=game_N;i++)
    {
      if ((subset)) wrong=i;
      if (wrong) break;
    }

    if (wrong!=0)
    {
      sprintf(lib_txt,"wrong number of soldiers on stair %d: %d requested, %d available",wrong,subset);
      lib_error(1,lib_txt);
    }

    /* decide */
    choice=decide(subset);

    /* choice 1: move subset one stair up, discard the rest */
    if (choice==1)
    {
      for (i=1;i<=game_N;i++) st;
      for (i=1;i<=game_N;i++) st;
    }
    else  /* choice 2: discard subset, move complement one stair up */
    {
      for (i=1;i<=game_N;i++) st;
      for (i=1;i<=game_N;i++) st;
    }

    /* check if there are any soldiers left */
    /* check if there is any soldier at position 1 */
    cnt=0;
    for (i=1;i<=game_N;i++) cnt+=(!!st);

    if (cnt==0)
    {
      sprintf(lib_txt,"You lost!");
      lib_error(0,lib_txt);
    }

    if (st)
    {
      sprintf(lib_txt,"You won!");
      lib_error(0,lib_txt);
    }

    return choice;
  }

---

A decorative fence

Richard just finished building his new house. Now the only thing the house misses is a cute little wooden fence. He had no idea how to make a wooden fence, so he decided to order one. Somehow he got his hands on the ACME1Fence Catalogue 2002, the ultimate resource on cute little wooden fences. After reading its preface he already knew, what makes a little wooden fence cute.

A wooden fence consists of N wooden planks, placed vertically in a row next to each other. A fence looks cute if and only if the following conditions are met:

• The planks have different lengths, namely 1, 2, ..., N plank length units.
• Each plank with two neighbors is either larger than each of its neighbors or smaller than each of them. (Note that this makes the top of the fence alternately rise and fall.)

It follows, that we may uniquely describe each cute fence with N planks as a permutation a₁,..., a_N of the numbers 1, ..., N such that (for all i;1<i<N) (a_i - a_i-1)*(a_i - a_i+1)>0 and vice versa, each such permutation describes a cute fence.

It is obvious, that there are many different cute wooden fences made of N planks. To bring some order into their catalogue, the sales manager of ACME decided to order them in the following way: Fence A (represented by the permutation a₁,..., a_N) is in the catalogue before fence B (represented by b₁, ..., b_N) if and only if there exists such i, that (for all j<i)(a_j=b_j) and a_i<b_i. (Also to decide, which of the two fences is earlier in the catalogue, take their corresponding permutations, find the first place on which they differ and compare the values on this place.) All the cute fences with N planks are numbe"#008DDC" (starting from 1) in the order they appear in the catalogue. This number is called their catalogue number.

All cute fences made of N = 4 planks, orde"#008DDC" by their catalogue numbers.

After carefully examining all the cute little wooden fences, Richard decided to order some of them. For each of them he noted the number of its planks and its catalogue number. Later, as he met his friends, he wanted to show them the fences he orde"#008DDC", but he lost the catalogue somewhere. The only thing he has got are his notes. Please help him find out, how will his fences look like.

Input description

The first line of the input file contains the number K (1<=K<=100) of input data sets. K lines follow, each of them describes one input data set.

Each of the following K lines contains two integers N and C (1<=N<=20), separated by a space. N is the number of planks in the fence, C is the catalogue number of the fence.

You may assume, that the total number of cute little wooden fences with 20 planks fits into a 64-bit signed integer variable (long long in C/C++, int64 in FreePascal). You may also assume that the input is correct, in particular that C is at least 1 and it doesn't exceed the number of cute fences with N planks.

Output description

For each input data set output one line, describing the C-th fence with N planks in the catalogue. More precisely, if the fence is described by the permutation a₁, ..., a_N, then the corresponding line of the output file should contain the numbers ai (in the correct order), separated by single spaces.

Example input

  2
  2 1
  3 3

Example output

  1 2
  2 3 1

---

A highway and the seven dwarfs

Once upon a time, there was a land where several families of dwarfs were living. This land was called Dwarfland. Each family lived in one house. Dwarfs were often visiting their friends from the other families. Because the Dwarfland was free of evil, it happened that each dwarf visited each other during some short period of time.

Once, the humans living in countries around Dwarfland decided to build several straight highways. As the humans weren't aware of the dwarfs, some of the planned highways passed through Dwarfland. The dwarfs discove"#008DDC" this and were quite unhappy about it. The dwarfs are very little, and also very slow, so they are unable to cross the highway safely.

The dwarfs managed to get the plans for the highways somehow, and now they need your help. They would like to keep on visiting each other, so they don't like those highways which divide their houses into two non-empty parts. After they find out which highways they don't like, they will magically prevent the humans from building them.

The dwarfs are very little, and cannot reach the keyboard. So they asked for your help.

Task

Given is a number N of points (houses) in the plane and several straight lines (highways). For each given line, your task is to determine whether all N points lie on the same side of the line or not. Your program has to output the answer for the currently processed line before reading the description of the next one. You may assume that no highway passes through any of the houses.

Input and output description

Your program is supposed to read the input from the standard input (stdin in C/C++, input in FreePascal) and write its output to the standard output (stdout in C/C++, output in FreePascal). The first line of the input contains one integer N (0<=N<=100 000). N lines follow, the i-th of them contains two real numbers x_i, y_i (-10⁹<=x_i, y_i<=10⁹) separated by a single space - the coordinates of the i-th house.

Each of the following lines contains four real numbers X₁, Y₁, X₂, Y₂ (-10⁹<=X₁, Y₁, X₂, Y₂<=10⁹) separated by a single space. These numbers are the coordinates of two different points , lying on the highway. For each line of input, your program is supposed to output a line containing the string "GOOD" if all of the given points are on the same side of the given line, or "BAD" if the given line divides the points. After writing out each line of the output, your program should flush the output buffer. In the following sections you may find an example on how to do this.

We will terminate your program after it gives the answer for the last highway. Your program is not supposed to terminate by itself. You may assume that there will be no more than 100 000 highways.

Input and output routines in C/C++

Reading one line (note that there is no space after the last %lf):

  double X_1, Y_1, X_2, Y_2;
  scanf(" %lf %lf %lf %lf",&X_1,&Y_1,&X_2,&Y_2);

Writing the output for one line:

  printf("GOOD\n"); fflush(stdout);

Input and output routines in FreePascal

Reading one line:

  var X_1, Y_1, X_2, Y_2 : double;
  read(X_1,Y_1,X_2,Y_2);

Writing the output for one line:

  writeln('GOOD'); flush(output);

Warning

You are adviced to use the double data type (in both C/C++ and FreePascal) to store real numbers. Note that when using real number arithmetics, rounding errors may occur. If you want to test, whether two real numbers x, y are equal, don't test whether x = y but whether |x-y|<e (where e is a small constant, 10^-4 will suffice).

Example input

  4
  0.0 0
  6.00 -0.001
  3.125 4.747
  4.747 0.47
  5 3 7 0
  4 -4.7 7 4.7
  4 47 4 94

Example output

  GOOD
  BAD
  BAD

---

Royal guards

Once upon a time, there was a kingdom. It had everything a kingdom needs, namely a king and his castle. The ground-plan of the castle was a rectangle that was divided into M×N unit squares. Some of the squares are walls, some of them are free. We will call each of the free squares a room. The king of our kingdom was extremely paranoid, so one day he decided to make hidden pits (with alligators at the bottom) in some of the rooms.

But this was still not enough. One week later, he decided to place as many guards as possible inside his castle. However, this won't be so simple. The guards are trained so that immediately after they see someone, they shoot at him. And so the king has to place the guards carefully, because if two guards would see each other, they would shoot at themselves! Also evidently the king can't place a guard into a room with a pit.

Two guards in a room see each other, so each room may contain at most one guard. Two guards in different rooms see each other if and only if the squares corresponding to their rooms are in the same row or in the same column of the plan of the castle and there is no wall between them. (The guard can see only in four directions, much like a rook in chess.)

Task

Your task is to find out, how many guards can the king place inside his castle (according to the rules above) and to find one possible assignment of that many guards into the rooms.

Input description

The first line of the input file contains two numbers M, N, 1<=M,N<=200 - the dimensions of the ground-plan of the castle. The i-th of the following M lines contains N numbers a_i,1, ..., a_i,N, separated by single spaces, where:

• a_i,j=0 means that the square is free (a room without a pit)
• a_i,j=1 means that the square contains a pit
• a_i,j=2 means that the square is a wall

Note that the first coordinate of a square is the row and the second one is the column.

Output description

The first line of the output file should contain the maximum number K of guards the king may place inside his castle. The following K lines should contain one possible assignment of K guards into the free rooms of the castle so that no two guards would see each other.

More precisely, the i-th of these lines should contain two integers r_i, c_i separated by a single space - the coordinates of the room where i-th guard will be placed (r_i is the row and c_i is the column).

Castle from the example input and one possible correct output

Example input

  3 4
  2 0 0 0
  2 2 2 1
  0 1 0 2

Example output

  2
  1 2
  3 3

---

Birthday party

John's birthday is approaching slowly, and as every year, John is going to organize a great garden party. He wants all his friends to come, but (sadly) he knows, that it is almost impossible. For example Susie left Steve last week, and it will be almost impossible to make both of them come. John spent most of the last week visiting his friends and asking them to come. He got some promises, but even more requests. ('If you invite me, you just have to invite my boyfriend!' exclaimed Veronica. 'If you invite the Burdiliak twins, don't expect me or Joseph to come!' stated Peter.) Suddenly, John realized, that it will be quite hard just to satisfy all the requests he got.

Task

You are given a description of the requests John got from his friends. Your task is to find a group of people such that if John invites the people in this group (and nobody else) to his party, all the requests he got will be satisfied. The requests are described in the following way:

• name is a request. This request is satisfied if and only if John invites name.
• -name is a request. This request is satisfied if and only if John doesn't invite name. (In both cases, name is a string of at most 20 lowercase letters without spaces.)
• If R1, ..., Rk are requests, then (R1 & ... & Rk) is a request. This request is satisfied if and only if all requests R1, ..., Rk are satisfied.
• If R1, ..., Rk are requests, then (R1 | ... | Rk) is a request. This request is satisfied if and only if at least one of the requests R1, ..., Rk is satisfied.
• If R1, R2 are requests, then (R1=>R2) is a request. This request is not satisfied if and only if R1 is satisfied and R2 is not satisfied.

Input description

You can find ten input files, called party1.in to party10.in, here.

On the first line of the input file is the number of John's friends F, next F lines contain their names, one per line. On the next line is the number of requests N. Each of the following N lines contains one request.

Output description

For each file partyX.in you have to produce the corresponding output file partyX.out, containing one correct solution. The first line of the output file will be the number K of people John should invite. The following K lines should contain their names, one per line. You may assume that each of the input files has a (not necessarily unique) solution. If there are more possible solutions, you may output any of them.

Example input

  3
  veronica
  steve
  dick
  3
  (veronica => dick)
  (steve => -veronica)
  (steve & dick)

Example output

  2
  steve
  dick

---