# First Round SOI 2015

## Overview

This contest is over.

congress‒/100‒/10‒/30‒/40‒/20
wordchain‒/100‒/20‒/30‒/50
audio‒/100‒/20‒/40‒/40
yurt‒/100‒/20‒/20‒/30‒/30
river‒/100‒/20‒/15‒/15‒/20‒/30
bazaar‒/100‒/100

The Kazhakh Cheese Congress (KCC) hosts mice from $M$ different regions of the country. The regions are numbered from $1$ to $N$. From each region $i$, there will be visiting $N_i$ experts for sheep’s cheese and $N_i$ experts for goat’s cheese. The participants of the congress are traditionally hosted in $Z$ two-bed rooms. $Z$ is the sum of all $N_i$ such that all rooms are fully occupied. The rooms are numbered from $1$ to $Z$. To encourage communication, the Organizing Committee of the Kazhakh Cheese Congress (OCKCC) aims to split up the participants into rooms according to a certain scheme: In each room there should be hosted an expert for sheep’s cheese and an expert for goat’s cheese, and those two mice should be from different regions. Can you help the OCKCC to accomplish this task?

### Subtask 1: Two Regions (10 points)

For this subtask it holds that $M=2$, and your program should decide if there is a possible splitting. Input —– The first line of the input contains a single integer $T$, the number of test cases. $T$ test cases follow. Each test case consists of a single line containing the two integers $N_{1}$ and $N_{2}$, separated by a single space.

#### Output

For the $i$-th of the $T$ inputs, print “Case #i:”, followed by “POSSIBLE” if splitting is possible and “IMPOSSIBLE” otherwise.

#### Constraints

• $1\leq N_{1},N_{2}\leq 1\,000\,000$
• $T = 100$, i.e. there are exactly $100$ test cases

#### Examples

Input:

2
1 1
1 2

Output:

Case #1: POSSIBLE
Case #2: IMPOSSIBLE

Comment:

The first example results in two two-bed rooms. One room hosts the goat’s cheese expert from region 1 and the sheep’s cheese expert from region 2 and the other room hosts the sheep’s cheese expert from region 1 and the goat’s cheese expert from region 2. The second example does not admit a splitting where no two experts from region 2 are hosted in the same room.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 2: More Regions (30 points)

For this subtask, $M$ can take on other values, and your program should decide, if there is a possible splitting. Input —– The first line of the input contains a single integer $T$. $T$ test cases follow. Each test case consists of a single line with the integer $M$, describing the number of regions, followed by the $M$ numbers $N_i$, separated by single spaces.

#### Output

For the $i$-th of the $T$ inputs, print “Case #i:”, followed by “POSSIBLE” if splitting is possible and “IMPOSSIBLE” otherwise.

#### Constraints

• $1\leq M\leq 40\,000$
• $1\leq N_i\leq 1\,000\,000$
• $T = 100$, d.h. es gibt genau $100$ Testfälle

#### Examples

Input:

2
3 2 1 1
3 4 2 1

Output:

Case #1: POSSIBLE
Case #2: IMPOSSIBLE

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 3: Explicit Scheme (40 points)

For this subtask, you program should print an explicit splitting of mice into rooms, if there is such a splitting. Input —– The first line of the input contains a single integer $T$. $T$ test cases follow. Each test case consists of a single line with the integer $M$, describing the number of regions, followed by the $M$ numbers $N_i$, separated by single spaces.

#### Output

For the $i$-th test case, print “Case #i: IMPOSSIBLE”, if there is no possible splitting. Otherwise print the line “Case #i:”, followed by $Z$ lines, where the $i$-th such line contains the integers $A_i$ and $B_i$. Each of those lines describes the mice hosted in one of the $Z$ two-bed rooms: The $i$-th room hosts an expert for sheep’s cheese from region $A_i$ together with an expert for goat’s cheese from region $B_i$.

There can be many different possible splittings. In this case, your program should print an arbitrary possible splitting.

#### Constraints

• $1\leq M\leq 200$
• $1\leq N_i\leq 200$
• $T = 100$, i.e. there are exactly $100$ test cases

#### Examples

Input:

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

Output:

Case #1:
1 3
2 1
3 4
4 2
Case #2:
1 2
2 1
3 1
1 3
Case #3: IMPOSSIBLE

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 4: More Categories (20 points)

The OCKCC is thinking about inviting $K\cdot N_i$ mice from each region, where $K\geq 1$. As the scheme, according to which the mice where splitted up into rooms has made a lot of sense so far, it should now be applied in a more general form. This means that for $K=2$, this new scheme is identical with the previous scheme. From each region there will visit $N_i$ mice from $K$ different categories (like experts for sheep’s cheese, goat’s cheese, spicy cheese, mild cheese, …). The categories are numbered from $1$ to $K$. Those mice should then be split up into $K$-bed rooms such that in each room there are no two mice from the same region and no two mice from the same category. (In particular, in each room there is exactly one mouse from each category.) Input —– The first line of the input contains a single integer $T$. $T$ test cases follow. Each test case consists of a single line with the integers $M$ and $K$, the number of regions and the number of categories respectively, followed by the $M$ integers $N_i$, separated by single spaces.

#### Output

For the $I$-th test case, print “Case #i: IMPOSSIBLE”, if there is no possible splitting. Otherwise print the line “Case #i:”, followed by $Z$ lines, where the $i$-th such line contains $K$ integers $R_{i,j}$. Each of those lines describes the mice hosted in one of the $Z$ $K$-bed rooms: Within the $i$-th room, the expert of category $j$ is from region $R_{i,j}$.

#### Constraints

• $1\leq M\leq 200$
• $1\leq K\cdot N_i\leq 400$
• $T = 100$, i.e. there are exactly $100$ test cases

#### Examples

Input:

3
3 2 2 1 1
3 3 2 1 1
3 3 1 1 1

Output:

Case #1:
1 2
2 1
3 1
1 3
Case #2: IMPOSSIBLE
Case #3:
3 1 2
1 2 3
2 3 1

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

Mouse Stofl wants to compose some novel poems that consist of nice word chains. His fancy idea is that he wants to use words that occur inside other words.

A word occurs in another word if all its letters appear in the same order inside the other word. For example: “Bach” occurs in “belauschen” but not in “hab”.

### Subtask 1: Two words (20 points)

At first. Stofl wants to compose a poem of length $2$. To do this he wants to know for two words whether one occurs in the other. Help him answer this question.

### Input

The first line contains the number $T$, the number of poems that Stofl wants to compose. After that $T$ lines, each containing two words, follow.

### Output

For each of the $T$ inputs you have to output a single line. Each line should start with “Case #i:”, followed by “YES”, if one of the two words occurs in the other and “NO”, if not.

### Constraints

• Each word consists of at most $10\,000$ small letters from a to z.
• $T = 100$, i.e. there are exactly $100$ poems.

### Examples

Input:

3
bach belauschen
belauschen bach
bach dach

Output:

Case #1: YES
Case #2: YES
Case #3: NO

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 2: Short poems (30 points)

Stofl now has an entire list of words in front of him and tries to find two of them that build a poem. Determine whether there are two words in the list that build a poem.

### Input

The first line contains the number $T$, the number of poems that Stofl wants to compose. $T$ inputs follow, each of them structured like this: The first line contains the number $N$. The next $N$ lines each contain a word $W_i$.

### Output

For each of the $T$ inputs you have to output a single line. Each line should start with “Case #i:”, followed by “YES”, if a poem of length $2$ exists abd “NO”, if not.

### Constraints

• $1 \le N \leq 400$, i.e. there are at most $400$ different words.
• Each word consists of at most $100$ small letters from a to z.
• $T = 100$, i.e. there are exactly $100$ poems.

### Examples

Input:

2
5
bach
dachs
belauschen
obacht
dach
4
bach
dach
fach
sache

Output:

Case #1: YES
Case #2: NO

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 3: Long poems (50 points)

After Stofl mastered the art of short poems, he now tries to write longer ones. Each poem consists of one nice word chain. A word chain is nice if each word occurs in all subsequent words. “ah, bach, belauschen” is a nice word chain, because “ah” occurs “bach” as well as in “belauschen”, and “bach” occurs in “belauschen”. “ah, bach, brach, belauschen” on the other hand is not nice, because “brach” does not occur in “belauschen”.

Stofl wants to compose long poems and nice long word chains for that. Given a list of words, try to find the length of the longest word chain.

### Input

The first line contains the number $T$, the number of poems that Stofl wants to compose. $T$ inputs follow, each of them structured like this: The first line contains the number $N$. The next $N$ lines each contain a word $W_i$.

### Ouptut

For each of the $T$ inputs, you have to output “Case #i:” followed by $L$, the length (number of words) of the longest word chain.

### Constraints

• $1 \le L \leq N \leq 400$, i.e. there are at most $400$ words and the solution is at most the number of words.
• Each word consists of at most $100$ small letters from a to z.
• $T = 100$, i.e. there are exactly $100$ poems.

### Examples

Input:

2
8
bach
dachs
brach
belauschen
obacht
ah
belauschend
dach
3
bach
dach
fach

Output:

Case #1: 4
Case #2: 1

Comment:

The only poem of length 4 in the first example is: „ah, bach, belauschen, belauschend“.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

Stofl is listening to a boring audio file. The talker speaks very slowly and Stofl wonders, if he might shorten the long sounds, in order to be done faster.

A “sound” is an interference of waves of different periods, resulting in a new wave with a longer period.

Stofl knows from his physics class, that the period of the resulting wave is given by the smallest common multiple of the single periods.

### Subtask 1: Single Interference (20 Punkte)

Given $N$ periods $P_j$, compute the period of the resulting wave for multiple test cases.

#### Input

The first line of the input contains the integer $L$, the number of test cases. $L$ lines follow. Each line starts with an integer $N$, the number of single waves. $N$ numbers $P_{1}$ up to $P_N$ follow, the single periods. Those are separated by single spaces.

#### Output

For the $i$-th test case, print “Case #i:”, followed by the number $P_r$, the resulting period.

#### Constraints

• $1\leq N\leq 10000$
• It is guaranteed that $1\leq P_r\leq 2^{63}$
• $L=100$ i.e. there are exactly $100$ test cases

#### Examples

Input:

3
3 6 8 4
2 8 4
4 10 3 5 2

Output:

Case #1: 24
Case #2: 8
Case #3: 30

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 2: Multiple Interferences (40 Punkte)

Stofl is thinking that a single sound can be shortened most (while keeping its character), by only playing one period in full, and attaching just the remainder of the wave.

If therefore a (resulting) wave of period $5$ ms is playing for $124$ ms in total, it goes through $24$ full periods with a remainder of $4$ ms. ($124/5 = 24$, with remainder $4$). The sound character would however be preserved by playing only one period and $4$ ms of the remainder, therefore the section could be shortened from $124$ ms to $5+4=9$ ms. Furthermore, Stofl only wants to hear relevant parts of the file. If a section of the file is completely silent, this section should therefore be removed from the file completely.

An audio file consists of $N$ single waves, having periods $P_e$, a starting time $T_s$ and an ending time $T_e$ and interfere accordingly. Your task is to shorten multiple files as described above. The resulting audio files will consist of $K$ sections ($K$ may differ for different files), in a certain order. Each section consists of a certain period $P_r$ and takes time $T_r$. Note, that two subsequent sections having the same period cannot be combined into one. (Because generally, the sound in one section will not be the same as the sound in the other section.)

#### Input

The first line of the input contains the number $L$, the number of files to be shortened. $L$ files follow: Each file is initiated by a line with the number $N$, the number of single waves. The following $N$ lines describe a single wave each: They contain for each single wave the integers $P_e$, $T_s$ and $T_e$, the period, the starting time and the ending time of this single wave.

#### Output

You should print the resulting audio files as follows: The first line of the $i$-th audio file contains “Case #i:”. The next line of a file contains two numbers $K$, the number of sections of this file and $T_s$, the time at which the first section starts. The following $K$ lines describe the sections in the order in which they will be played. One line consists of the two numbers $P_r$ and $T_r$, i.e. the resulting period and the duration of the section.

#### Constraints

• $1\leq N\leq 1000$
• For all single waves it holds that $0\leq T_s< T_e\leq 10^{9}$.
• It is guaranteed that $1\leq P_r\leq 2^{63}$.
• $L=100$ i.e. there are exactly $100$ files.

### Examples

Input:

3
3
15 20 120
2 0 20
6 1 150
2
7 2 101
11 23 123
2
2 1 2
3 3 10

Output:

Case #1:
4 0
2 1
6 7
30 40
6 6
Case #2:
3 2
7 7
77 78
11 11
Case #3:
2 1
2 1
3 4

Comment:

Explanation of the first file: From time 0 to 1 only the wave with period 2 is active, which can’t be shortened. From time 1 to 20 are two waves with periods 2 and 6 active, which results in a wave with period 6. The 20=3·6+1 seconds can be reduced to 6+1=7 seconds. From time 20 to 120, the resulting period is 30 (from periods 6 and 30), so the 100=3·30 + 10 seconds can be reduced to 30+10=40. From 120 to 150 only the wave with period 6 is active, which can be reduced to 6 seconds.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 3: Big Files and Big Periods (40 Punkte)

The task description for this subtask corresponds to the task description of subtask 2, but you do not have to print the entire file explicitly.

Rather, for the $i$-th section of the file, print $P_r$ modulo $M$, where $M=10^{9}+7=1000000007$ and $P_r$ is the period of the $i$-th section of the file. $a$ modulo $b$ corresponds to the positive integer remainder of the division of $a$ by $b$. In other words, $0\leq a$ modulo $b, and if $a$ modulo $b = c$, then there is an integer $d$ such that $a=d\cdot b+c$.

(The shortened durations are no longer of any importance.)

#### Input

The first line of the input contains the number $L$, the number of files. $L$ files follow: Each file is initiated by a line with the number $N$, the number of single waves. The following $N$ lines describe a single wave each: They contain for each single wave the numbers $P_e$, $T_s$ and $T_e$, the period, the starting time and the ending time of the single wave.

#### Output

The first line of the $i$-th output contains”Case #i:”. The next line of a file contains the two numbers $K$, the number of sections of this file and $T_s$, the time at which the first section starts. The following $K$ lines describe the sections in the order, in which they are played. A line consists of the single number $P_r$ modulo $M$, i.e. the resulting period modulo $M$.

#### Constraints

• $1\leq N\leq 10\,000\,000$
• For all single waves, it holds that $P_e\leq 2^{20}$ and $0\leq T_s.
• $L=100$ i.e. there are extactly $100$ files

Input:

1
4
1000000007 1 2
1000000008 1 4
1000000009 1 4
1000000010 3 4

Output:

Case #1:
3 1
0
2
3

Since the input file for this subtask is huge, we will correct this task by hand. In order to allow you to test your solution on small inputs, we still provide a judging system. Please note, that the automated response is not final and you will be awarded points (if any) only after the submission deadline.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

The nomadic people in Kazakhstan often live in yurts. A yurt is a traditional, big, round tent. On your trip you discovered a big campground. It has $N$ spots, numbered from $1$ to $N$. On each spot, exactly one yurt is located. Also the yurts are numbered from $1$ to $N$, such that a yurt and a spot always go together. But the yurts got mixed up as they were assembled in a hurry in the middle of the night. Now not necessarily all yurts are standing on the spot with the same number. Your task is to sort the yurts, so that they are in the right order again. You can do this step by step, always tearing down, switching and reassembling two yurts in each step. You can never dismount more than two yurts at once, so only swap two yurts at a time. Your goal is to use as few swaps as possible to bring the yurts into the correct order.

### Subtask 1: Practical part with few yurts (20 points)

In this subtask the campground includes at most $8$ yurts. It is your task to bring them in the correct order with as few swaps as possible. Your output gets accepted if you need at most $N$ swaps for $N$ yurts. So your program does not necessarily need to act optimally. For instance, if the tents are already in sorted order at the beginning, it is ok to do no swaps at all or to perform a few dummy swaps back and forth. You will think about the fact that $N$ swaps are always sufficient in subtask 3.

### Input

The first line contains the number $T$, the number of test cases. The following $T$ lines each describe a test case. Each line starts with $N$ the number of yurts, followed by $N$ space-separated numbers, $M_{1}$ to $M_N$, where $M_i$ is the number of the yurt, that is place on spot $i$ initially.

### Output

For each test case print one line with a possible sequence of $N$ or less swaps. For the $t$-th test case start the line with “Case #t:”, followed by an even number of space-separated numbers $M_i$. These numbers mean that in your $i$-th swap the yurt on spot $M_{2i-1}$ get interchanged with the yur on spot $M_{2i}$. (Example: $5$ $2$ $3$ $6$ $4$ $3$ means that the yurts on spot $5$ and $2$ get swaped. After that the yurts on spot $3$ and $6$, and finally the ones on spots $4$ and $3$).

### Constraints

• $3 \leq N \leq 8$, so there are between $3$ and $8$ yurts.
• You are allowed to perform at most $N$ swaps.
• $T = 100$, so there are $100$ test cases.

### Beispiele

Input:

2
3 1 3 2
5 4 3 2 5 1

Output:

Case #1: 2 3
Case #2: 1 5 2 3 4 5

Illustration of the second example: The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 2: Practical part with many yurts (20 points)

In this subtask the campground includes at most $500$ yurts. It is your task to bring them in the correct order with as few swaps as possible. Your output gets accepted if you need at most $N$ swaps for $N$ yurts. So your program does not necessarily need to act optimally.

The format of the input and output is identical with subtask 1.

### Constraints

• $3 \leq N \leq 500$, so there are between $3$ and $5\,000$ yurts.
• You are allowed to perform at most $N$ swaps.
• $T = 100$, so there are $100$ test cases.

### Beispiele

Input:

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

Output:

Case #1: 1 5 2 3 4 5
Case #2: 2 3 3 4 2 4 3 4 1 10

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 3: Theoretical part: at most $N-1$ swap (30 points)

The mouse Stofl now claims, that it is always possible to bring $N$ yurts with strictly less than $N$ (so at most $N-1$) swaps into the correct order. Describe how your algorithm solves this task and explain why you need less than $N$ swaps for every possible initial placement.

We expect you to explain and justify your solution as continuous text. Try to convince you and us that your idea really works. For this and the next subtask your submission does not necessarily need to include a complete compilable program. A precise explanation, e.g. with pseudo code, is enough.

The contest is over, you can no longer submit.

### Subtask 4: optimal number of swaps (30 points)

You are not happy with just doing it in less than $N$ swaps, as for some initial placements it is possible to do it much faster. Can you argue for your algorithm that it acts always optimally? You should justify why every imaginable strategy needs at least as many swaps as yours.

The contest is over, you can no longer submit.

Note: You can implement and explain different approaches for the subtasks, if you want. If you find a solution for subtask 4 it is possible that you can use the same approach to solve the other subtasks as well.

In Kazakhstan there are some gigantic rivers. The river Irtysch for example is over $4\,000$ kilometers long. It originates in China, flows through Kazakhstan and leads into the Ob in Russia. Along the Irtysch there are numerous cities. They are numbered from $1$ to $N$. Each city has two districts, one on the left and one of the right side of the stream with a bridge that connects the two districts. Unfortunately, at a recent flooding all $N$ bridges collapsed.

To temporarily reestablish some connections across the river some ferries between given pairs of cities are planned. In order for the ferries to be able to land in the cities, each city has to construct exactly one dock. In each city, this dock can be built either on the left or each side of the city. Each city should have a dock, even if there is no ferry connection including it.

No new bridges across the river are planned. If one wants to cross the river one does have to use the ferry. In order for it to be as easy as possible to cross the river as many ferry connections as possible should cross the river, i.e. depart and land on different river sides. A ferry connection from city $A$ to city $B$ crosses the river for example, if the dock in $A$ is on the left and in $B$ is on the right side of the river. But if both docks are on the same side than this ferry does not cross the river.

Now the mayors of these cities have to decide on which side to construct their docks. Can you help them build their docks so that as many ferries as possible cross the river?

### Subtask 1: Only river-crossing ferry connections (total 50 points)

In this first subtask we want to study the case when it is possible to choose the docks such that all ferry connections cross the river. To do this we first simplify the task by assuming the following: If one wants to travel from city $A$ to city $B$ only using ferries (independent of the river side at the start and end), then there is exactly one or zero ways to do this. This shall hold for every pair of cities $A$ and $B$. This also includes indirect connections: If there is a connection from $A$ to $C$ and from $C$ to $B$, you can for example assume that there is no direct connection from $A$ to $B$ but also no other city $D$, that is connected to both $A$ and $B$. #### Subtask 1a: Implementation (20 points)

Can you write a program that constructs the docks under this simplification such that all ferry connection cross the river?

#### Input

The first line contains the number $T$, the number of test cases. The following $T$ test cases are all formatted like this: one the first line there are the numbers $N$ and $M$ separated by a space, being the number of cities $N$ and the number of ferry connections $M$. After that follow $M$ lines, each containing two space-separated numbers $a$ and $b$, describing that there is a ferry connection from city $a$ to city $b$.

#### Ausgabe

For each of the $T$ test cases output “Case #t:” followed by $N$ letters, each $L$ or $R$. The letter $i$-th of these letters indicates on which side the dock in city $i$ should get built.

#### Constraints

• $1 \leq N \leq 1\,000$
• $0 \leq M \leq 1\,000$
• $T = 100$

#### Examples

Input:

1
6 4
1 2
3 4
3 5
3 6

Output:

Case #1: LRLRRR The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

#### Subtask 1b: Justification (15 points)

Please argue why your program from subtask 1a is correct? Why can you guarantee that always all connections cross the river? What is the runtime and memory complexity of your program?

The contest is over, you can no longer submit.

#### Subtask 1c: Relaxation of the condition (15 points)

Your friend mouse stofl has found this new example and is surprised that it does not satisfy our condition from above (there are two paths from city $1$ to city $4$, either directly or through the cities $2$ and $3$), but it is possible that all connections cross the river nevertheless.

#### Example

Input:

1
4 4
1 2
2 3
3 4
4 1

Output:

Case #1: LRLR Can you find a better condition that describes exactly when it is possible that all ferry connections cross the river? Describe an algorithms that solves such instances and analyze it.

The contest is over, you can no longer submit.

### Subtask 2: at least half of it river-crossing (total 50 points)

Now let’s get rid off all conditions and let’s look at an arbitrary set of ferry connections. Mouse Stofle already found an example, where it is not possible to let all connections cross the river:

#### Example

Input:

1
4 4
1 2
2 3
1 3
2 4

Output:

Case #1: LRRL However you pick the docks at most three of the four connections will cross the river.

Stofl claims that it is possible to always pick the docks, such that at least half of all connections cross the river for any set of ferry connections. Is that really true? Can you find an algorithm that does that and can you argue why?

#### Subtask 2a: Implementation (20 points)

Write a program, that picks the docks such that at least half of all the ferry connections cross the river.

The format of the input and output is identical to subtask 1a.

#### Constraints

• $1 \leq N \leq 1\,000$
• $0 \leq M \leq 1\,000$
• $T = 100$

#### Example

Input:

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

Output:

Case #1: LRLRL

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

#### Subtask 2b: Justification (30 points)

Argue why your algorithm from subtask 2a is correct. Analyze its runtime and memory consumptions.

The contest is over, you can no longer submit.

Note: You can implement and describe different approaches for each subtask if you want, of course.

This summer mouse Stofl was in Alamaty, the biggest city in Kasachstan. He was really impressed by the bazaar where he bought some diamonds. Those diamonds are sold using a special auction: every potential buyer chooses an amount of gold nuggets he wants to bid. The highest bid gets a diamond, but everyone has to pay their bid. To make it a bit more interesting and to prevent the richest from getting all the diamonds there is an additional rule: every person is only allowed to spend a given amount of gold nuggets during an auction.

Mouse Stofl will travel again to Alamaty to cheer for the swiss IOI team. He wants to visit the diamonds auction again. Help him to buy as much diamonds as possible with the allowed amount of gold nuggets.

### The game

There are in total $A$ auctions. During each auction $D$ diamonds are auctioned. (This allows your program to analyze the strategies of the other programs and to develop a counter strategy). In each auction you have $G$ gold nuggets you are allowed to spend.

An auction consists of $D$ bid rounds. In each of those rounds each player bids covered his bid $B$ (i.e. the other players don’t know what your bid is). The player with the highest bid receives a diamond. If multiple players have the same highest bid then the diamonds will be sawed up resulting in one piece of the same size for every of those players. Every player has to pay their bid every round no matter who won. The sum of all bids of one player during one auction may not exceed $G$.

### Input / Output

Your program will be started by a game server. It has to read from stdin and output the moves to stdout.

On game start you receive one line with four space separated integers: $N$, the number of players (incl. your program); $A$, the number of auctions; $D$, the number of bid rounds per auction (which corresponds to the number of diamonds); and $G$, the number of gold nuggets per auction you are allowed to spend.

Afterwards $A$ auctions are played. In each there are $D$ bid rounds. A bid round looks like this:

1. You output an integer $B$, the amount if gold nuggets you want to bid on the active diamond. 1. You receive one line with $N-1$ space separated integers, the bids of the other players for the active diamond. The order of the players stays the same during the whole game.

As soon as $A$ auctions were played your program should exit.

### Examples

> 3 1 3 1000
< 100
> 20 80
< 50
> 70 80
< 25
> 120 80


Explanation: There are 3 players in total. In the first round you bid 100 gold nuggets, the other two players bid 20 and 80 gold nuggets respectively. You receive one diamond. After the three rounds each player owns one diamond.

### Constraints

• $2 \leq N \leq 10$
• $1 \leq A \leq 1000$
• $1 \leq D \leq 1000$
• $1 \leq G \leq 10^{9}$

### Evaluation

The evaluation for the creativity task is different from the one for the other tasks. You get

• 30 % of the points for a program which plays the game correctly i.e. it respects the rules and plays at least as good as the sample bots.
Important: It is not allowed to simply submit the code of a sample bot. However it is allowed and recommended to use them as an example how to properly perform input/output in your programming language.
• The remaining 70% of the points will be rewarded according to the performance during the tournament on the SOI day.

So please optimize your program not only so that it wins against the sample bots, then we will also test it against the submissions of the other participants.

This year you are allowed to submit multiple programs (maximum 3 per participant) and your best program will be used for the ranking. Bundle these programs in a zip archive and submit that. The last submission counts for this task!

This year you are allowed to submit multiple programs (maximum 3 per participant, your last 3 submissions count) and your best program will be used for the ranking. We want to encourage you with this to implement riskier strategies as well as to try out several different strategies.

### Hints

For interactive tasks it is important to flush the output buffer after every round to ensure that the server can see your output.

Use the following commands:

• C/C++: fflush(stdout);
• C++: cout << flush;
• Pascal: flush(output);
• There are similar commands in other languages.

Furthermore it is important that your program does not wait for more characters than the server provides you as input. Especially spaces and line breaks in C format strings are a frequent source of errors. For example if you read the last variable of the input with scanf("\%d ", &x);, the scanf function will wait for the next char which is not a space or a line break. However you will only receive such a char after you provided your next move. To solve this use instead scanf("\%d", &x); (no whitespaces after \%d).

### Sample bots, server and visualization

During the first round we will provide the following material:

• sample bots in various programming languages.
• a server program you can use to let your program compete against itself or another program.
• a visualization to view simulated games.