Problem A: AntiGlobalists

A group of AntiGlobalists has decided to move to a new village on the boundary of a huge forest.

The arrangement of houses and paths in the village turned out to be a major problem: Many of the AntiGlobalists are friends and want to visit each other often, so they want to have a path between their houses. However the AntiGlobalists are also known for quarreling with everyone else. To avoid the chance of meeting with someone they do not like, it is required that no two paths intersect - there should be no crossroads in the village (And of course also no other means of crossing; overpasses spoil the scenery and underpasses destroy the root systems of precious herbs.) . Each AntiGlobalist also wants to be able to visit the forest, of course without having to cross any path - i.e., it is also necessary to make it possible to get from each house to ``infinity'' without crossing a path.

You are given a description of the relationships between AntiGlobalists. Your task is to decide whether such an ideal village can be built.

Input Specification

The input consists of several instances.

The first line of each instance contains two integers 1 <= H <= 10 000 and F >= 0 separated by a single space. H is the number of AntiGlobalists. The AntiGlobalists have assigned integers between 0 and H - 1. F is the number pairs of friends. The following F lines of the instance describe the pairs of friends. Each of the lines contains two integers 0 <= h1, h2 < H separated by a single space, meaning that AntiGlobalists with numbers h1 and h2 are friends. Each pair of friends is described exactly once.

The instances follow each other immediately, without any separator. The input is terminated by a line containing two zeros.

Output Specification

The output consists of several lines. The i-th line of the output corresponds to the i-th instance. If it is possible to build a village for the corresponding input instance, the output line consists of ``Yes, village can be built'' string. If it is not possible to build such a village, the output line consists of ``No, village cannot be built'' string.

Sample Input

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

Sample Output

Yes, village can be built
No, village cannot be built

Problem B: Boatherds

Boatherds Inc. is a sailing company operating in the country of Trabantustan and offering boat trips on Trabantian rivers. All the rivers originate somewhere in the mountains and on their way down to the lowlands they gradually join and finally the single resulting river flows to the sea. Moreover, the Trabantian villages are exactly at the rivers' springs, junctions and at the mouth of the largest river. Please note that more than 2 rivers can join at a junction. However, the rivers always form a tree (with villages as vertices).

The pricing policy of the Boatherds is very simple: each segment of each river between two villages is assigned a price (the price is same in both directions), so if a tourist requests a journey between any two villages, the ticket office clerks just add the prices of the segments along the only path between the villages.

One day, a very strange tourist appeared. She told the clerks that she returns to her country on the next day and she wants to spend all the remaining money on a boat trip, so they should find a route with exactly this cost. Being just poor (ahem) businessmen, they have asked the Abacus Calculator Makers for help.

You are given a description of the river network with costs of river segments and a sequence of integers x1,..., xk. For each xi, you should determine if there is a pair of cities (a, b) in the river network such that the cost of the trip between a and b is exactly xi.

Input Specification

The input consists of several instances. Each instance is described by (in the following order):

The whole input is ended by a single line containing the number 0.

Output Specification

For each instance you should produce a sequence of M lines (where M is the number of queries in the particular instance). The i-th of these lines contains the word ``AYE'' if there exists a pair of cities in the river network which is connected by a path of cost xi, or the word ``NAY'' otherwise.

Output for each instance must be followed by a single line containing just the dot character.

Sample Input

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

Sample Output

AYE
AYE
NAY
AYE
.

Problem C: C Looooops

A Compiler Mystery: We are given a C-language style for loop of type

for (variable = A; variable != B; variable += C)
  statement;

I.e., a loop which starts by setting variable to value A and while variable is not equal to B, repeats statement followed by increasing the variable by C. We want to know how many times does the statement get executed for particular values of A, B and C, assuming that all arithmetics is calculated in a k-bit unsigned integer type (with values 0 <= x < 2k) modulo 2k.

Input Specification

The input consists of several instances. Each instance is described by a single line with four integers A, B, C, k separated by a single space. The integer k (1 <= k <= 32) is the number of bits of the control variable of the loop and A, B, C (0 <= A, B, C < 2k) are the parameters of the loop.

The input is finished by a line containing four zeros.

Output Specification

The output consists of several lines corresponding to the instances on the input. The i-th line contains either the number of executions of the statement in the i-th instance (a single integer number) or the word FOREVER if the loop does not terminate.

Sample Input

3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0

Sample Output

0
2
32766
FOREVER

Problem D: God of the Vile Baskers

A not very famous writer Arthur Conan Moyle has finally found out why his books are not as popular as he believes they would deserve. He noticed that his works are getting a bit boring due to frequent repetitions of same or similar pieces of text. He decided that the best way how to improve the quality of his books is to simply throw away everything after the first repetition - the books then get an interesting open-ended feeling.

First he attempted to look for exactly same pieces of text, but this failed, since the repeated texts often do not match precisely - some of letters that are lowercase in the first place may be uppercase in the second and vice versa, punctuation may be a bit different, and even the words in sentences may be in slightly different order. To overcome these problems, he devised the following more involved criterion for recognizing duplicates (a positive integer k is a parameter of his criterion; by changing it he affects how long repeated pieces are still acceptable):

Alphabetic characters are the letters 'a'-'z' and 'A'-'Z'. We do not distinguish case of the letters, i.e. 'a' is supposed to be the same letter as 'A'.

Two strings S1 and S2 are k-identical up to permutation of letters if:

In other words, if the strings S1 and S2 are k-identical up to permutation of letters, then the alphabetic characters in them are the same, but their ordering may be different.

Your task is to write a program that separates a longest initial part that does not contain two substrings k-identical up to permutation of letters from several of the ACM's books.

Input Specification

The input consists of several instances. Each instance is described by two lines.

The first line of the instance consists of an integer number 1 <= k <= 50. The second line of the instance consists of the string T. Length of T is at most 100 000 characters. The string T may contain non-alphabetic characters including spaces, but it does not contain any characters with special meaning (i.e. with ASCII code smaller than 32).

The input is terminated by a line containing a zero.

Output Specification

The output consists of several lines. The i-th line of the output corresponds to the i-th input instance. The line a single integer number - length of the longest prefix P (including all non-alphabetic characters) of the string T of the corresponding instance such that P does not contain two distinct, but not necessarily non-overlapping, substrings S1 and S2 that are k-identical up to permutation of letters.

Sample Input

4
a'B'C'd'x'a'b'c'd
4
abcdabcd
0

Sample Output

16
4

Problem E: Electricity

Blackouts and Dark Nights (also known as ACM++) is a company that provides electricity. The company owns several power plants, each of them supplying a small area that surrounds it. This organization brings a lot of problems - it often happens that there is not enough power in one area, while there is a large surplus in the rest of the country.

ACM++ has therefore decided to connect the networks of some of the plants together. At least in the first stage, there is no need to connect all plants to a single network, but on the other hand it may pay up to create redundant connections on critical places - i.e. the network may contain cycles. Various plans for the connections were proposed, and the complicated phase of evaluation of them has begun.

One of the criteria that has to be taken into account is the reliability of the created network. To evaluate it, we assume that the worst event that can happen is a malfunction in one of the joining points at the power plants, which might cause the network to split into several parts. While each of these parts could still work, each of them would have to cope with the problems, so it is essential to minimize the number of parts into which the network will split due to removal of one of the joining points.

Your task is to write a software that would help evaluating this risk. Your program is given a description of the network, and it should determine the maximum number of non-connected parts from that the network may consist after removal of one of the joining points (not counting the removed joining point itself).

Input Specification

The input consists of several instances.

The first line of each instance contains two integers 1 <= P <= 10 000 and C >= 0 separated by a single space. P is the number of power plants. The power plants have assigned integers between 0 and P - 1. C is the number of connections. The following C lines of the instance describe the connections. Each of the lines contains two integers 0 <= p1, p2 < P separated by a single space, meaning that plants with numbers p1 and p2 are connected. Each connection is described exactly once and there is at most one connection between every two plants.

The instances follow each other immediately, without any separator. The input is terminated by a line containing two zeros.

Output Specification

The output consists of several lines. The i-th line of the output corresponds to the i-th input instance. Each line of the output consists of a single integer C. C is the maximum number of the connected parts of the network that can be obtained by removing one of the joining points at power plants in the instance.

Sample Input

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

Sample Output

1
2
2

Problem F: Firepersons

The Association for Courtly Manners, an international organization for standardization of social interactions (Better known under the name Absurdly Clumsy Moralists, but let's not take prejudice.) has decided to create a new international standard defining ranks of firepersons (Formerly firemen, but the international standards of course must be politically correct.) - each fireperson receives an integer number describing his rank and when they arrive to a fire, they must enter the fire ground in order of increasing ranks and the low ranked firepersons must keep the fire burning long enough for the high ranked firepersons to enjoy extinguishing sufficiently.

The ranks are assigned according to an Arbitrary Constant Multiplier Sequence. An ACM-sequence of order k is an integer sequence defined by its first k terms a0, a1,...ak-1 and a recurrence relation mod 10 000 for n >= k, where the bi's are integer constants. The i-th oldest fireperson then gets rank ai.

Your task is to calculate the rank of the i-th fireperson, given parameters of the ACM-sequence and the number i.

Input Specification

The input consists of several instances. Each instance is described on a single line containing the following integers separated by a single space: k, a0, , ak-1, b1, , bk, i. Here 1 <= k <= 100 is the order of the sequence, 0 <= ai < 10 000 are the first k elements of the sequence, 0 <= bi < 10 000 are the multipliers and 0 <= i < 1 000 000 000 is the number of the element we ask for.

The input ends with a line containing a number 0.

Output Specification

The output consists of several lines corresponding to the instances on the input. The l-th line contains a single integer ai which is the i-th element of the sequence described by the l-th input instance.

Sample Input

2 0 1 1 1 6
0

Sample Output

8