## uva524

maksyuki 发表于 oj 分类，标签:

A ring is composed of n (even number) circles as shown in diagram. Put natural numbers 1, 2, . . . , n into each circle separately, and the sum of numbers in two adjacent circles should be a prime. Note: the number of first circle should always be 1.
Input
n (0 < n ≤ 16)
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements.
You are to write a program that completes above process.
Sample Input
6
8
Sample Output
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

## uva10976

maksyuki 发表于 oj 分类，标签:

It is easy to see that for every fraction in the form 1/k(k > 0), we can always find two positive integers x and y, x ≥ y, such that: 1/k= 1/x + 1/y
Now our question is: can you write a program that counts how many such pairs of x and y there are for any given k?
Input
Input contains no more than 100 lines, each giving a value of k (0 < k ≤ 10000).
Output
For each k, output the number of corresponding (x, y) pairs, followed by a sorted list of the values of x and y, as shown in the sample output.
Sample Input
2
12
Sample Output
2
1/2 = 1/6 + 1/3
1/2 = 1/4 + 1/4
8
1/12 = 1/156 + 1/13
1/12 = 1/84 + 1/14
1/12 = 1/60 + 1/15
1/12 = 1/48 + 1/16
1/12 = 1/36 + 1/18
1/12 = 1/30 + 1/20
1/12 = 1/28 + 1/21
1/12 = 1/24 + 1/24

## uva11059

maksyuki 发表于 oj 分类，标签:

Given a sequence of integers S = {S1, S2, . . . , Sn}, you should determine what is the value of the maximum positive product involving consecutive terms of S. If you cannot find a positive sequence, you should consider 0 as the value of the maximum product.
Input
Each test case starts with 1 ≤ N ≤ 18, the number of elements in a sequence. Each element Si is an integer such that −10 ≤ Si ≤ 10. Next line will have N integers, representing the value of each element in the sequence. There is a blank line after each test case. The input is terminated by end of file (EOF).
Output
For each test case you must print the message: ‘Case #M: The maximum product is P.’, where M is the number of the test case, starting from 1, and P is the value of the maximum product. After each test case you must print a blank line.
Sample Input
3
2 4 -3
5
2 5 -1 2 -1
Sample Output
Case #1: The maximum product is 8.
Case #2: The maximum product is 20.

## uva725

maksyuki 发表于 oj 分类，标签:

Write a program that finds and displays all pairs of 5-digit numbers that between them use the digits 0 through 9 once each, such that the first number divided by the second is equal to an integer N, where 2 ≤ N ≤ 79. That is,
abcde / fghij = N, where each letter represents a different digit. The first digit of one of the numerals is allowed to be
zero.
Input
Each line of the input file consists of a valid integer N. An input of zero is to terminate the program.
Output
Your program have to display ALL qualifying pairs of numerals, sorted by increasing numerator (and, of course, denominator). Your output should be in the following general form:
xxxxx / xxxxx = N
xxxxx / xxxxx = N
.
.
In case there are no pairs of numerals satisfying the condition, you must write ‘There are no solutions for N.’. Separate the output for two different values of N by a blank line.
Sample Input
61
62
0
Sample Output
There are no solutions for 61.
79546 / 01283 = 62
94736 / 01528 = 62

## Codeforces Round #486(Div.3) (6/6)

maksyuki 发表于 比赛 分类，标签:

A Diverse Team
There are n students in a school class, the rating of the i-th student on Codehorses is ai. You have to form a team consisting of k students (1≤k≤n) such that the ratings of all team members are distinct.

If it is impossible to form a suitable team, print "NO" (without quotes). Otherwise print "YES", and then print k distinct numbers which should be the indices of students in the team you form. If there are multiple answers, print any of them.

Input
The first line contains two integers n and k (1≤k≤n≤100) — the number of students and the size of the team you have to form.

The second line contains n integers a1,a2,…,an (1≤ai≤100), where ai is the rating of i-th student.

Output
If it is impossible to form a suitable team, print "NO" (without quotes). Otherwise print "YES", and then print k distinct integers from 1 to n which should be the indices of students in the team you form. All the ratings of the students in the team should be distinct. You may print the indices in any order. If there are multiple answers, print any of them.

Assume that the students are numbered from 1 to n.

Examples
input
5 3
15 13 15 15 12
output
YES
1 2 5
input
5 4
15 13 15 15 12
output
NO
input
4 4
20 10 40 30
output
YES
1 2 3 4
Note
All possible answers for the first example:

{1 2 5}
{2 3 5}
{2 4 5}
Note that the order does not matter.

B Substrings Sort
You are given n strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are its substrings.

String a is a substring of string b if it is possible to choose several consecutive letters in b in such a way that they form a. For example, string "for" is contained as a substring in strings "codeforces", "for" and "therefore", but is not contained as a substring in strings "four", "fofo" and "rof".

Input
The first line contains an integer n(1 ≤ n ≤ 100) — the number of strings.

The next nlines contain the given strings. The number of letters in each string is from 1 to 100, inclusive. Each string consists of lowercase English letters. Some strings might be equal.

Output
If it is impossible to reorder n given strings in required order, print "NO" (without quotes). Otherwise print "YES" (without quotes) and n given strings in required order.

Examples
input
5
a
aba
abacaba
ba
aba
output
YES
a
ba
aba
aba
abacaba
input
5
a
abacaba
ba
aba
abab
output
NO
input
3
qwerty
qwerty
qwerty
output
YES
qwerty
qwerty
qwerty
Note
In the second example you cannot reorder the strings because the string "abab" is not a substring of the string "abacaba".

C Equal Sums
You are given k sequences of integers. The length of the i-th sequence equals to ni. You have to choose exactly two sequences i and j(i ≠ j) such that you can remove exactly one element in each of them in such a way that the sum of the changed sequence i(its length will be equal to ni−1) equals to the sum of the changed sequence j(its length will be equal to nj−1).

Note that it's required to remove exactly one element in each of the two chosen sequences.

Assume that the sum of the empty (of the length equals 0) sequence is 0.

Input
The first line contains an integer k(2 ≤ k ≤ 2⋅10^5) — the number of sequences.

Then k pairs of lines follow, each pair containing a sequence.

The first line in the i-th pair contains one integer ni(1 ≤ ni < 2⋅10^5) — the length of the i-th sequence.

The second line of the i-th pair contains a sequence of ni integers ai,1, ai,2, …, ai,n i.

The elements of sequences are integer numbers from −104 to 104.

The sum of lengths of all given sequences don't exceed 2⋅10^5, i.e. n1+n2+⋯+nk ≤ 2⋅10^5.

Output
If it is impossible to choose two sequences such that they satisfy given conditions, print "NO" (without quotes). Otherwise in the first line print "YES" (without quotes), in the second line — two integers i, x(1 ≤ i ≤ k, 1 ≤ x ≤ ni), in the third line — two integers j, y(1 ≤ j ≤ k, 1 ≤ y ≤ nj). It means that the sum of the elements of the i-th sequence without the element with index x equals to the sum of the elements of the j-th sequence without the element with index y.

Two chosen sequences must be distinct, i.e. i ≠ j. You can print them in any order.

If there are multiple possible answers, print any of them.

Examples
input
2
5
2 3 1 3 2
6
1 1 2 2 2 1
output
YES
2 6
1 2
input
3
1
5
5
1 1 1 1 1
2
2 3
output
NO
input
4
6
2 2 2 2 2 2
5
2 2 2 2 2
3
2 2 2
5
2 2 2 2 2
output
YES
2 2
4 1
Note
In the first example there are two sequences
[2, 3, 1, 3, 2] and [1, 1, 2, 2, 2, 1]. You can remove the second element from the first sequence to get [2,
1, 3, 2] and you can remove the sixth element from the second sequence to get [1, 1, 2, 2, 2]. The sums of the both resulting sequences equal to 8, i.e. the sums are equal.

D Points and Powers of Two
There are n distinct points on a coordinate line, the coordinate of i-th point equals to xi. Choose a subset of the given set of points such that the distance between each pair of points in a subset is an integral power of two. It is necessary to consider each pair of points, not only adjacent. Note that any subset containing one element satisfies the condition above. Among all these subsets, choose a subset with maximum possible size.

In other words, you have to choose the maximum possible number of points xi1, xi2, …, xim such that for each pair x
ij, xik it is true that |xij−xik| = 2^d where d is some non-negative integer number (not necessarily the same for each pair of points).

Input
The first line contains one integer n(1 ≤ n ≤ 2⋅10^5) — the number of points.

The second line contains n pairwise distinct integers x1, x2, …, xn(−10^9 ≤ xi ≤10^9) — the coordinates of points.

Output
In the first line print m — the maximum possible number of points in a subset that satisfies the conditions described above.

In the second line print m integers — the coordinates of points in the subset you have chosen.

If there are multiple answers, print any of them.

Examples
input
6
3 5 4 7 10 12
output
3
7 3 5
input
5
-1 2 5 8 11
output
1
8
Note
In the first example the answer is [7, 3, 5]. Note, that |7 − 3| = 4 = 2^2, |7 − 5| = 2 = 2^1 and |3 − 5| = 2 = 2^1
. You can't find a subset having more points satisfying the required property.

E Divisibility by 25
You are given an integer n from 1 to 10^18 without leading zeroes.

In one move you can swap any two adjacent digits in the given number in such a way that the resulting number will not contain leading zeroes. In other words, after each move the number you have cannot contain any leading zeroes.

What is the minimum number of moves you have to make to obtain a number that is divisible by 25 ? Print -1 if it is impossible to obtain a number that is divisible by 25.

Input
The first line contains an integer n(1 ≤ n ≤ 10^18). It is guaranteed that the first (left) digit of the number
n is not a zero.

Output
If it is impossible to obtain a number that is divisible by 25, print -1. Otherwise print the minimum number of moves required to obtain such number.

Note that you can swap only adjacent digits in the given number.

Examples
input
5071
output
4
input
705
output
1
input
1241367
output
-1
Note
In the first example one of the possible sequences of moves is 5071 → 5701 → 7501 → 7510 →7150.

## uva10562

maksyuki 发表于 oj 分类，标签:

Professor Homer has been reported missing. We suspect that his recent research works might have had something to with this. But we really don’t know much about what he was working on! The detectives tried to hack into his computer, but after hours of failed efforts they realized that the professor had been lot more intelligent than them. If only they could realize that the professor must have been absent minded they could get the clue rightaway. We at the crime lab were not at all surprised when the professor’s works were found in a 3.5” floppy disk left inside the drive.

The disk contained only one text file in which the professor had drawn many trees with ASCII characters. Before we can proceed to the next level of investigation we would like to match the trees drawn with the ones that we have in our database. Now you are the computer geek —we leave this trivial task for you. Convert professor’s trees to our trees.

Input

The first line of the input file (which you can assume comes from standard input) contains the number of trees, T (1 ≤ T ≤ 20) drawn in the file. Then you would have T trees, each ending with a single hash (‘#’) mark at the beginning of the line. All the trees drawn here are drawn vertically in top down fashion. The labels of each of node can be any printable character except for the symbols ‘-’, ‘|’, ‘ ’ (space) and ‘#’. Every node that has children has a ‘|’ symbol drawn just below itself. And in the next line there would be a series of ‘-’ marks at least as long as to cover all the immediate children. The sample input section will hopefully clarify your doubts if there is any. No tree drawn here requires more than 200 lines, and none of them has more than 200 characters in one line.

Output

Our trees are drawn with parenthesis and the node labels. Every subtree starts with an opening parenthesis and ends with a closing parenthesis; inside the parenthesis the node labels are listed. The sub trees are always listed from left to right. In our database each tree is written as a single string in one line, and they do not contain any character except for the node labels and the parenthesis pair. The node labels can be repeated if the original tree had such repetitions.

Sample Input

2
A
|
--------
B C D
| |
----- -
E F G
#
e
|
----
f g
#

Sample Output

(A(B()C(E()F())D(G())))

(e(f()g()))

## Codeforces Round #485(Div.2) (6/6)

maksyuki 发表于 比赛 分类，标签:
A Infinity Gauntlet
You took a peek on Thanos wearing Infinity Gauntlet. In the Gauntlet there is a place for six Infinity Gems:
the Power Gem of purple color, the Time Gem of green color, the Space Gem of blue color, the Soul Gem of orange color, the Reality Gem of red color, the Mind Gem of yellow color.
Using colors of Gems you saw in the Gauntlet determine the names of absent Gems.
In the first line of input there is one integer n(0 ≤ n ≤ 6) — the number of Gems in Infinity Gauntlet.
Input
In next n lines there are colors of Gems you saw. Words used for colors are: purple, green, blue, orange, red, yellow. It is guaranteed that all the colors are distinct. All colors are given in lowercase English letters.

Output
In the first line output one integer m(0 ≤ m ≤ 6) — the number of absent Gems.

Then in m lines print the names of absent Gems, each on its own line. Words used for names are: Power, Time, Space, Soul, Reality, Mind. Names can be printed in any order. Keep the first letter uppercase, others lowercase.

Examples
input
4
red
purple
yellow
orange
output
2
Space
Time
input
0
output
6
Time
Mind
Soul
Power
Reality
Space
Note
In the first sample Thanos already has Reality, Power, Mind and Soul Gems, so he needs two more: Time and Space.

In the second sample Thanos doesn't have any Gems, so he needs all six.

B  High School: Become Human
Year 2118. Androids are in mass production for decades now, and they do all the work for humans. But androids have to go to school to be able to solve creative tasks. Just like humans before.
It turns out that high school struggles are not gone. If someone is not like others, he is bullied. Vasya-8800 is an economy-class android which is produced by a little-known company. His design is not perfect, his characteristics also could be better. So he is bullied by other androids.
One of the popular pranks on Vasya is to force him to compare x^y with y^x. Other androids can do it in milliseconds while Vasya's memory is too small to store such big numbers.
Please help Vasya! Write a fast program to compare x^y with y^x for Vasya, maybe then other androids will respect him.
Input
On the only line of input there are two integers x and y(1≤ x, y ≤ 10^9).
Output
If x^y < y^x , then print '<' (without quotes). If x^y > y^x, then print '>' (without quotes). If x^y = y^x, then print '=' (without quotes).
Examples
input
5 8
output
>
input
10 3
output
<
input
6 6
output
=
Note
In the first example 5^8 = 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 ⋅ 5 = 390625, and 8^5 = 8 ⋅ 8 ⋅ 8 ⋅ 8 ⋅ 8 = 32768. So you should print '>'.
In the second example 10^3 = 1000 < 3^10 = 59049.
In the third example 6^6 = 46656 = 6^ 6.

C Three displays
It is the middle of 2018 and Maria Stepanovna, who lives outside Krasnokamensk (a town in Zabaikalsky region), wants to rent three displays to highlight an important problem.

There are  n displays placed along a road, and the  i-th of them can display a text with font size si
only. Maria Stepanovna wants to rent such three displays with indices i<j<k that the font size increases if you move along the road in a particular direction. Namely, the condition si < sj < sk should be held.

The rent cost is for the i-th display is ci. Please determine the smallest cost Maria Stepanovna should pay.

Input
The first line contains a single integer n(3 ≤ n ≤ 3000) — the number of displays.

The second line contains n integers s1, s2, …, sn(1 ≤ si ≤ 10^9) — the font sizes on the displays in the order they stand along the road.

The third line contains n integers c1, c2, …, cn(1 ≤ ci ≤ 10^8) — the rent costs for each display.

Output
If there are no three displays that satisfy the criteria, print -1. Otherwise print a single integer — the minimum total rent cost of three displays with indices i < j < k such that si < sj < sk.

Examples
input
5
2 4 5 4 10
40 30 20 10 40
output
90
input
3
100 101 100
2 4 5
output
-1
input
10
1 2 3 4 5 6 7 8 9 10
10 13 11 14 15 12 13 13 18 13
output
33
Note
In the first example you can, for example, choose displays 1,  4 and 5, because s1 < s4 < s5(2 < 4 < 10), and the rent cost is  40 + 10 + 40 = 90.

In the second example you can't select a valid triple of indices, so the answer is -1.

D Fair
Some company is going to hold a fair in Byteland. There are n towns in Byteland and m two-way roads between towns. Of course, you can reach any town from any other town using roads. There are  k types of goods produced in Byteland and every town produces only one type. To hold a fair you have to bring at least s different types of goods. It costs d(u, v) coins to bring goods from town u to town v where d(u, v) is the length of the shortest path from u to v. Length of a path is the number of roads in this path.

The organizers will cover all travel expenses but they can choose the towns to bring goods from. Now they want to calculate minimum expenses to hold a fair in each of n towns.

Input
There are 4 integers n, m, k, s in the first line of input (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5, 1 ≤ s ≤ k ≤ min(n, 100)) — the number of towns, the number of roads, the number of different types of goods, the number of different types of goods necessary to hold a fair.

In the next line there are n integers a1, a2, …, an(1 ≤ ai ≤ k), where ai is the type of goods produced in the i-th town. It is guaranteed that all integers between 1 and k occur at least once among integers ai.

In the next m lines roads are described. Each road is described by two integers u v(1 ≤ u, v ≤ n, u ≠ v) — the towns connected by this road. It is guaranteed that there is no more than one road between every two towns. It is guaranteed that you can go from any town to any other town via roads.

Output
Print n numbers, the i-th of them is the minimum number of coins you need to spend on travel expenses to hold a fair in town i. Separate numbers with spaces.

Examples
input
5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5
output
2 2 2 2 3
input
7 6 3 2
1 2 3 3 2 2 1
1 2
2 3
3 4
2 5
5 6
6 7
output
1 1 1 2 2 1 1
Note
Let's look at the first sample.

To hold a fair in town 1 you can bring goods from towns 1(0 coins), 2(1 coin) and 4(1 coin). Total numbers of coins is 2.

Town 2: Goods from towns 2(0), 1(1), 3(1). Sum equals 2.

Town 3: Goods from towns 3(0), 2(1), 4(1). Sum equals 2.

Town 4: Goods from towns 4(0), 1(1), 5(1). Sum equals 2.

Town 5: Goods from towns 5(0), 4(1), 3(2). Sum equals 3.

E Petr and Permutations
Petr likes to come up with problems about randomly generated data. This time problem is about random permutation. He decided to generate a random permutation this way: he takes identity permutation of numbers from 1 to n and then 3n times takes a random pair of different elements and swaps them. Alex envies Petr and tries to imitate him in all kind of things. Alex has also come up with a problem about random permutation. He generates a random permutation just like Petr but swaps elements 7n + 1 times instead of 3n times. Because it is more random, OK?!

You somehow get a test from one of these problems and now you want to know from which one.

Input
In the first line of input there is one integer n(10^3 ≤ n ≤ 10^6).

In the second line there are n distinct integers between 1 and n— the permutation of size n from the test.

It is guaranteed that all tests except for sample are generated this way: First we choose n— the size of the permutation. Then we randomly choose a method to generate a permutation — the one of Petr or the one of Alex. Then we generate a permutation using chosen method.

Output
If the test is generated via Petr's method print "Petr" (without quotes). If the test is generated via Alex's method print "Um_nik" (without quotes).

Example
input
5
2 4 5 1 3
output
Petr
Note
Please note that the sample is not a valid test (because of limitations for n) and is given only to illustrate input/output format. Your program still has to print correct answer to this test to get AC. Due to randomness of input hacks in this problem are forbidden.

F AND Graph
You are given a set of size m with integer elements between 0 and 2^n − 1 inclusive. Let's build an undirected graph on these integers in the following way: connect two integers x and y with an edge if and only if x&y = 0. Here & is the bitwise AND operation. Count the number of connected components in that graph.

Input
In the first line of input there are two integers n and m(0 ≤ n ≤ 22, 1 ≤ m ≤ 2^n).

In the second line there are m integers a1, a2, …, am(0 ≤ ai < 2^n) — the elements of the set. All ai are distinct.

Output
Print the number of connected components.

Examples
input
2 3
1 2 3
output
2
input
5 5
5 19 10 20 12
output
2

## uva10129

maksyuki 发表于 oj 分类，标签:

Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.

There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word ‘acm’ can be followed by the word ‘motorola’. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.

Input

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number N that indicates the number of plates (1 ≤ N ≤ 100000). Then exactly N lines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters ‘a’ through ‘z’ will appear in the word. The same word may appear several times in the list.

Output

Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.

If there exists such an ordering of plates, your program should print the sentence ‘Ordering is possible.’. Otherwise, output the sentence ‘The door cannot be opened.’

Sample Input

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

Sample Output

The door cannot be opened.

Ordering is possible.

The door cannot be opened.

## uva10305

maksyuki 发表于 oj 分类，标签:

John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is only possible if other tasks have already been executed.

Input

The input will consist of several instances of the problem. Each instance begins with a line containing two integers, 1 ≤ n ≤ 100 and m. n is the number of tasks (numbered from 1 to n) and m is the number of direct precedence relations between tasks. After this, there will be m lines with two integers i and j, representing the fact that task i must be executed before task j.

An instance with n = m = 0 will finish the input.

Output

For each instance, print a line with n integers representing the tasks in a possible order of execution.

Sample Input

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

Sample Output

1 4 2 5 3

## uva816

maksyuki 发表于 oj 分类，标签:

The 1999 World Finals Contest included a problem based on a dice maze. At the time the problem was written, the judges were unable to discover the original source of the dice maze concept. Shortly after the contest, however, Mr. Robert Abbott, the creator of numerous mazes and an author on the subject, contacted the contest judges and identified himself as the originator of dice mazes. We regret that we did not credit Mr. Abbott for his original concept in last years problem statement. But we are happy to report that Mr. Abbott has offered his expertise to this years contest with his original and unpublished walk-through arrow mazes.

As are most mazes, a walk-through arrow maze is traversed by moving from intersection to intersection until the goal intersection is reached. As each intersection is approached from a given direction, a sign near the entry to the intersection indicates in which directions the intersection can be exited. These directions are always left, forward or right, or any combination of these.

Figure 1 illustrates a walk-through arrow maze. The intersections are identified as (row, column) pairs, with the upper left being (1,1). The Entrance intersection for Figure 1 is (3,1), and the Goal intersection is (3,3). You begin the maze by moving north from (3,1). As you walk from (3,1) to (2,1), the sign at (2,1) indicates that as you approach (2,1) from the south (traveling north) you may continue to go only forward. Continuing forward takes you toward (1,1). The sign at (1,1) as you approach from the south indicates that you may exit (1,1) only by making a right. This turns you to the east now walking from (1,1) toward (1,2). So far there have been no choices to be made. This is also the case as you continue to move from (1,2) to (2,2) to (2,3) to (1,3). Now, however, as you move west from (1,3) toward (1,2), you have the option of continuing straight or turning left. Continuing straight would take you on toward (1,1), while turning left would take you south to (2,2). The actual (unique) solution to this maze is the following sequence of intersections: (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3).

You must write a program to solve valid walk-through arrow mazes. Solving a maze means (if possible) finding a route through the maze that leaves the Entrance in the prescribed direction, and ends in the Goal. This route should not be longer than necessary, of course.

Input

The input file will consist of one or more arrow mazes. The first line of each maze description contains the name of the maze, which is an alphanumeric string of no more than 20 characters. The next line contains, in the following order, the starting row, the starting column, the starting direction, the goal row, and finally the goal column. All are delimited by a single space. The maximum dimensions of a maze for this problem are 9 by 9, so all row and column numbers are single digits from 1 to 9. The starting direction is one of the characters N, S, E or W, indicating north, south, east and west, respectively.

All remaining input lines for a maze have this format: two integers, one or more groups of characters, and a sentinel asterisk, again all delimited by a single space. The integers represent the row and column, respectively, of a maze intersection. Each character group represents a sign at that intersection. The first character in the group is ‘N’, ‘S’, ‘E’ or ‘W’ to indicate in what direction of travel the sign would be seen. For example, ‘S’ indicates that this is the sign that is seen when travelling south. (This is the sign posted at the north entrance to the intersection.) Following this first direction character are one to three arrow characters. These can be ‘L’, ‘F’ or ‘R’ indicating left, forward, and right, respectively.

The list of intersections is concluded by a line containing a single zero in the first column. The next line of the input starts the next maze, and so on. The end of input is the word ‘END’ on a single line by itself.

Output

For each maze, the output file should contain a line with the name of the maze, followed by one or more lines with either a solution to the maze or the phrase ‘No Solution Possible’. Maze names should start in column 1, and all other lines should start in column 3, i.e., indented two spaces. Solutions should be output as a list of intersections in the format (R,C) in the order they are visited from the start to the goal, should be delimited by a single space, and all but the last line of the solution should contain exactly 10 intersections.

Note: Figure 2: Robert Abbott’s Atlanta Maze Robert Abbotts walk-through arrow mazes are actually intended for large-scale construction, not paper. Although his mazes are unpublished, some of them have actually been built. One of these is on display at an Atlanta museum. Others have been constructed by the American Maze Company over the past two summers. As their name suggests these mazes are intended to be walked through.

For the adventurous, Figure 2 a graphic of Robert Abbotts Atlanta maze. Solving it is quite difficult, even when you have an overview of the entire maze. Imagine trying to solve this by actually walking through the maze and only seeing one sign at a time! Robert Abbott himself indicated that the maze is too complex and most people give up before finishing. Among the people that did not give up was Donald Knuth: it took him about thirty minutes to solve the maze.

The first maze in the following sample input is the maze in Figure 1.

Sample Input

SAMPLE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION
3 1 N 3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
END

Sample Output

SAMPLE

(3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1)

(2,2) (1,2) (1,3) (2,3) (3,3)

NOSOLUTION

No Solution Possible