## Problem A. Aerodynamics ≡

 Author: NEERC-2008 Jury Input file: aerodynamics.in Time limit: 2 sec Output file: aerodynamics.out Memory limit: 64 Mb

### Statement

Bill is working in a secret laboratory. He is developing missiles for national security projects. Bill is the head of the aerodynamics department.

One surprising fact of aerodynamics is called Whitcomb area rule. An object flying at high-subsonic speeds develops local supersonic airflows and the resulting shock waves create the effect called wave drag. Wave drag does not depend on the exact form of the object, but rather on its cross-sectional profile.

Consider a coordinate system with OZ axis pointing in the direction of object's motion. Denote the area of a section of the object by a plane z=z0 as S(z0). Cross-sectional profile of the object is a function S that maps z0 to S(z0). There is a perfect aerodynamic shape called Sears-Haack body. The closer cross-sectional profile of an object to the cross-sectional profile of Sears-Haack body, the less wave drag it introduces. That is an essence of Whitcomb area rule.

Bill's department makes a lot of computer simulations to study missile's aerodynamic properties before it is even built. To approximate missile's cross-sectional profile one takes samples of S(z0) for integer arguments z0 from zmin to zmax.

Your task is to find the area S(z0) for each integer z0 from zmin to zmax, inclusive, given the description of the missile. The description of the missile is given to you as a set of points. The missile is the minimal convex solid containing all the given points. It is guaranteed that there are four points that do not belong to the same plane.

### Input file format

The first line of the input file contains three integer numbers: n, zmin and zmax. The following n lines contain three integer numbers each: x, y, and z coordinates of the given points. All coordinates do not exceed 100 by their absolute values. No two points coincide. There are four points that do not belong to the same plane.

### Output file format

For each integer z0 from zmin to zmax, inclusive, output one floating point number: the area S(z0). The area must be precise to at least 5 digits after decimal point.

### Constraints

4 ≤ n ≤ 100

0 ≤ zmin ≤ zmax ≤ 100

### Sample tests

No. Input file (aerodynamics.in) Output file (aerodynamics.out)
1
9 0 5
0 0 5
-3 0 2
0 -1 2
3 0 2
0 1 2
2 2 0
2 -2 0
-2 -2 0
-2 2 0
16.00000
14.92000
10.08000
4.48000
1.12000
0.00000

## Problem B. Blind Walk ≡

 Author: ACM ICPC NEERC 2008 Jury | Roman Elizarov Input file: standard input Time limit: 2 sec Output file: standard output Memory limit: 256 Mb

### Statement

ВНИМАНИЕ: на момент добавления задачи CATS не поддерживала интерактивные задачи. Поэтому проверка решений по этой задаче не производится.

This is an interactive problem.

Your task is to write a program that controls a robot which blindly walks through a maze. The maze is n × m (1 ≤ n, m ≤ 30) rectangular grid that consists of square cells. Each cell is either empty or blocked. All cells on the border of the maze are blocked. The robot starts in an empty cell. It can move south, west, north, or east to an adjacent empty cell. The robot is blind and has only bump sensors, so when it attempts to move it can either succeed or bump into blocked cell and fail.

The robot has to visit all empty cells in the maze. All cells are guaranteed to be reachable.

The picture shows sample maze where blocked cells are, filled and initial robot's location is designated with a circle.

The program must write to the standard output one line with robot's action and wait for a line in the standard input with a response, then write next action and read next response, and so on until all empty cells in the maze had been visited. The program must exit only when all cells have been visited. Empty cells may be visited multiple times. It is acceptable to move even after all cells had been visited.

### Input file format

Each line of the standard input represents response on robot's action. It is either a string \t{EMPTY} if robot has successfully moved in the specified direction to an adjacent cell or a string \t{BLOCKED} if robot's movement has failed because the corresponding adjacent cell was blocked.

### Output file format

Each line of the standard output represents robot's action. It is one of the following five strings: \t{SOUTH}, \t{WEST}, \t{NORTH}, \t{EAST}, or \t{DONE}. \t{DONE} must be printed when the robot has visited all empty cells. After printing \t{DONE} your program must exit. You must flush standard output after printing each action.

### Sample tests

No. Input file (standard input) Output file (standard output)
1
NORTH
EAST
SOUTH
EAST
SOUTH
WEST
SOUTH
WEST
NORTH
WEST
WEST
NORTH
EAST
NORTH
DONE
BLOCKED
BLOCKED
EMPTY
BLOCKED
BLOCKED
EMPTY
BLOCKED
BLOCKED
EMPTY
EMPTY
BLOCKED
BLOCKED
EMPTY
BLOCKED

## Problem C. Clock ≡

 Author: NEERC-2008 Jury Input file: clock.in Time limit: 2 sec Output file: clock.out Memory limit: 64 Mb

### Statement

One famous Russian architect plans to build a new monumental construction. It will be a huge clock that indicates the time from the beginning of the universe.

The face of this clock contains hands, moving at constant speeds. They are numbered from 1 to n from the fastest to the slowest one. The fastest hand makes one revolution per minute (60 seconds). Each next hand moves slower than previous, the (i+1)-th hand makes one revolution when the i-th hand makes di revolutions.

The setting mechanism of this clock is very simple. You can take a hand by the handle, located on its end, and move it in any direction. When you move the hand, slower hands are moving in proportion to their usual speeds, and faster hands are not moving. Remember that hands are huge, so setting this clock is a hard job.

Consider an example with three hands: a second hand, a minute hand, and an hour hand. Their lengths are 5, 15 and 10 meters respectively. You want to set the clock from 2:30 to 6:00 (fig.1). The easiest way to do it is to rotate the minute hand 180 clockwise, and then move the hour hand 90 clockwise. The total distance you moved the handles of the hands is approximately 62.83 meters.

Your task is to write a program that finds the way to set the clock that minimizes the total distance you have to move the handles.

### Input file format

The first line of the input file contains one integer n — the number of hands. The second line contains n1 integer numbers d1, d2, …, dn1. The third line contains n integer numbers l1, l2, …, ln — lengths of clock hands. Next two lines contain two non-negative integer numbers (one number per line): time indicated by the clock and the actual time that should be set. Both times are measured in seconds from the beginning of the universe and are less than 263.

### Output file format

Print the minimal possible total distance you have to move the handles. The answer must be precise to at least 4 digits after decimal point.

0 < n ≤ 50

2 ≤ di ≤ 106

1 ≤ li ≤ 106

### Sample tests

No. Input file (clock.in) Output file (clock.out)
1
3
60 12
5 15 10
52200
453600
62.831853072

## Problem D. Drive through MegaCity ≡

 Author: NEERC-2008 Jury Input file: drive.in Time limit: 2 sec Output file: drive.out Memory limit: 256 Mb

### Statement

MegaCity of the future is a rectangular grid of streets. Each intersection has integer Cartesian coordinates x and y. To get from intersection a with coordinates xa, ya to intersection b with coordinates xb, yb you need to drive exactly |xaxb| + |yayb| blocks. Usually, it takes 10 time units to drive one block, so one can easily compute the time it takes to get from a to b. However, traffic jams that occur in MegaCity turn estimation of minimal driving time into a complex problem that you have to solve.

Traffic jams in MegaCity affect a rectangular area that is specified by coordinates of its bottom-left and top-right corners. The time to travel one block in the traffic jam is specified. All streets that are strictly inside the rectangular region are affected by the traffic jam. Sometimes, it is better to drive around the traffic jams to save time, but sometimes it is better to drive through some traffic jams as shown in the example — 17 blocks are driven outside of traffic jams, taking 10 time units per block, and 2 blocks in the light traffic jam with 11 time units per block.

### Input file format

The first line of the input file contains four integer numbers xa, ya, xb, and yb — coordinates of the start and finish intersections. The second line of the input file contains a single integer number n which specifies the number of traffic jams. The following n lines describe traffic jams. Each traffic jam is described by five integer numbers x1,i, y1,i, x2,i, y2,i and ti, where first four numbers are coordinates of the bottom-left and top-right corners of the jammed area, and ti is the time it takes to travel one block inside this traffic jam.

### Output file format

Write to the output file a single integer — the minimal driving time from intersection a to intersection b.

### Constraints

0 ≤ n ≤ 1000

(x1,i < x2,i, y1,i < y2,i)

10 < ti ≤ 108

All coordinates in the input file are from 0 to 108 inclusive. Areas of traffic jams neither intersect nor touch each other. Start and finish points are different and do not lie inside nor on the border of any traffic jam.

### Sample tests

No. Input file (drive.in) Output file (drive.out)
1
1 6 15 3
4
2 1 3 7 44
5 2 10 4 33
8 5 11 9 22
12 1 14 8 11
192

## Problem E. Exclusive Access ≡

 Author: NEERC-2008 Jury Input file: exclusive.in Time limit: 2 sec Output file: exclusive.out Memory limit: 64 Mb

### Statement

One important problem in concurrent programming is to ensure exclusive access to shared resources by multiple threads. It is also known as Mutual Exclusion protocol. A code that needs to be protected from concurrent execution is called critical section (CS). In order to coordinate access to CS, application threads use a set of shared variables to send information to each other. These shared variables are distinct from all the variables that are used by application code. In practice, mutual exclusion protocol is implemented as two methods — enterCS and exitCS. When application needs to execute some code in CS, it calls enterCS, then executes CS, then calls exitCS.

For theoretical analysis of mutual exclusion protocol one must consider running application as a whole. Each thread of application is represented as an infinite loop that repeatedly performs some work unrelated to CS, which is called non-critical section (NCS), then calls enterCS, then executes CS, then calls exitCS, then the loop repeats. The code inside NCS and CS is not relevant; it is considered to perform no operations related to the protocol and does not modify shared variables used by the protocol.

We consider a system with two concurrently running threads. Threads use a set of shared one-bit variables to implement mutual exclusion protocol. Each variable can store a value of zero or one that can be read or written by a single instruction. Shared variables are initialized to zero. Each thread has a local pointer to the instruction (IP) that it is going to execute next. Execution starts from the top of the code. During each step of execution one of the threads is arbitrarily chosen, it executes one instruction, and then changes its IP to the next instruction to execute. This infinite sequence of steps is called history. A history is called legal if either both threads execute infinitely many steps or just one thread does, while the other thread, having taken a finite number of steps, stops with IP at NCS.

The table below contains several algorithms in pseudo-code that attempt to implement mutual exclusion protocol. In this pseudo-code id is 0 for the first thread and 1 for the second. Variables want[0], want[1], and turn are shared between threads to implement mutual exclusion protocol. Lines marked with "\verb|+|" implement enterCS, lines marked with "\verb|-|" implement exitCS. Lines NCS() and CS() are placeholders for some code that works inside non-critical and critical sections respectively and is not relevant for this problem.

The task is to figure out if the given algorithm satisfies three important properties:

• The algorithm satisfies mutual exclusion if in any legal history CS is not executed concurrently by two threads (that is, there is no step where IP of both threads is at CS).
• The algorithm satisfies deadlock freedom if any legal history has infinitely many executions of CS.
• The algorithm satisfies starvation freedom if in any legal history a thread that executes infinitely many steps has infinitely many executions of CS.

The property of mutual exclusion is trivial. The algorithm that simply loops forever doing nothing will satisfy it. The sample algorithms above all satisfy mutual exclusion, but the first two fail to achieve deadlock freedom. The algorithm 3 (originally created by Gary Peterson) satisfies all three properties.

### Input file format

The input file starts with a line with two integer numbers — m1 and m2, where mi is the number of lines of code for i-th thread (2 ≤ mi ≤ 9). It is followed by m1 lines with the code for the first thread and m2 lines with the code for the second thread.

The code for each thread contains one instruction per line. Instruction starts with an integer line number from 1 to mi (lines are numbered in ascending order and are included to aid readability), followed by instruction mnemonic, followed by a list of instruction arguments, all separated by spaces. The last arguments of instruction represent line numbers of the next instructions to execute (NIP — from 1 to mi). There are three variables shared between threads — A, B, and C. Instruction mnemonics are:

• NCS — non-critical section placeholder. Its single argument is NIP.
• CS — critical section placeholder. Its single argument is NIP.
• SET — write value to the shared variable. It has three arguments v, x, and g, where v is the variable to write (A, B, or C), x is the value to write (0 or 1), and g is NIP.
• TEST — read and test the value of the shared variable. It has three arguments v, g0, and g1 where v is the variable to read (A, B, or C), g0 is NIP if the value of the variable is zero, and g1 is NIP if the value of the variable is one.

NCS and CS appear in the code for each thread exactly once. The code may or may not represent a simple loop, but is guaranteed to alternate executions of CS and NCS by one thread, that is, in every legal history two executions of CS by one thread always have NCS execution by the same thread in between and, vice versa, two executions of NCS by one thread have CS execution by the same thread in between.

First of three samples below represent algorithms 1-3 from the problem statement. Forth sample is an algorithm (originally created by Leslie Lamport) that uses just two shared bits (A and B) and satisfies mutual exclusion and deadlock freedom, but is not free from starvation. The last two samples are trivial algorithms. First one never executes CS nor NCS and thus guarantees mutual exclusion, but does not have deadlock freedom, nor starvation freedom properties. Second one loops between NCS and CS, thus fails to achieve mutual exclusion, but is free from deadlock and starvation.

### Output file format

Write to the output file a string of three letters. Letters represent properties of mutual exclusion, deadlock freedom, and starvation freedom. Write letter Y if the corresponding property is satisfied and N otherwise.

### Sample tests

No. Input file (exclusive.in) Output file (exclusive.out)
1
4 4
1 NCS 2
2 TEST C 3 2
3 CS 4
4 SET C 1 1
1 NCS 2
2 TEST C 2 3
3 CS 4
4 SET C 0 1
YNN
2
5 5
1 NCS 2
2 SET A 1 3
3 TEST B 4 3
4 CS 5
5 SET A 0 1
1 NCS 2
2 SET B 1 3
3 TEST A 4 3
4 CS 5
5 SET B 0 1
YNN
3
7 7
1 NCS 2
2 SET A 1 3
3 SET C 1 4
4 TEST B 6 5
5 TEST C 6 4
6 CS 7
7 SET A 0 1
1 NCS 2
2 SET B 1 3
3 SET C 0 4
4 TEST A 6 5
5 TEST C 4 6
6 CS 7
7 SET B 0 1
YYY
4
5 7
1 NCS 2
2 SET A 1 3
3 TEST B 4 3
4 CS 5
5 SET A 0 1
1 NCS 2
2 SET B 1 3
3 TEST A 6 4
4 SET B 0 5
5 TEST A 2 5
6 CS 7
7 SET B 0 1
YYN
5
3 3
1 SET A 0 1
2 CS 2
3 NCS 3
1 TEST A 1 1
2 CS 2
3 NCS 3
YNN
6
2 2
1 CS 2
2 NCS 1
1 NCS 2
2 CS 1
NYY

## Problem F. Fibonacci System ≡

 Author: ACM ICPC NEERC 2008 Jury Input file: fibonacci.in Time limit: 2 sec Output file: fibonacci.out Memory limit: 256 Mb

### Statement

Author: Anton Maydell Text: Andrew Lopatin Tests: Anton Maydell

Little John studies numeral systems. After learning all about fixed-base systems, he became interested in more unusual cases. Among those cases he found a Fibonacci system, which represents all natural numbers in an unique way using only two digits: zero and one. But unlike usual binary scale of notation, in the Fibonacci system you are not allowed to place two \t{1}s in adjacent positions.

One can prove that if you have number N = an an1… a1F in Fibonacci system, its value is equal to N = an ⋅ Fn + an1 ⋅ Fn1 + … + a1 ⋅ F1, where Fk is a usual Fibonacci sequence defined by F0=F1=1, Fi=Fi1+Fi2.

For example, first few natural numbers have the following unique representations in Fibonacci system:

1 = 1F, 2 = 10F, 3 = 100F, 4 = 101F, 5 = 1000F, 6 = 1001F, 7 = 1010F,

John wrote a very long string (consider it infinite) consisting of consecutive representations of natural numbers in Fibonacci system. For example, the first few digits of this string are 110100101100010011010...

He is very interested, how many times the digit \t{1} occurs in the N-th prefix of the string. Remember that the N-th prefix of the string is just a string consisting of its first N characters.

Write a program which determines how many times the digit 1 occurs in N-th prefix of John's string.

### Input file format

The input file contains a single integer N (0≤ N≤ 1015).

### Output file format

Output a single integer — the number of 1s in N-th prefix of John's string.

### Sample tests

No. Input file (fibonacci.in) Output file (fibonacci.out)
1
21
10

## Problem G. Giant Screen ≡

 Author: ACM ICPC NEERC 2008 Jury | Roman Elizarov Input file: giant.in Time limit: 2 sec Output file: giant.out Memory limit: 256 Mb

### Statement

You are working in Advanced Computer Monitors (ACM), Inc. The company is building and selling giant computer screens that are composed from multiple smaller screens. Your are responsible for design of the screens for your customers.

Customers order screens of the specified horizontal and vertical resolution in pixels and a specified horizontal and vertical size in millimeters. Your task is to design a screen that has a required resolution in each dimension or more, and has required size in each dimension or more, with a minimal possible price. The giant screen is always built as a grid of monitors of the same type. The total resolution, size, and price of the resulting screen is simply the sum of resolutions, sizes, and prices of the screens it is built from.

You have a choice of regular monitor types that you can order and you know their resolutions, sizes, and prices. The screens of each type can be mounted both vertically and horizontally, but the whole giant screen must be composed of the screens of the same type in the same orientation. You can use as many screens of the chosen type as you need.

### Input file format

The first line of the input file contains four integer numbers rh, rv, sh, and sv (all from 100 to 104 inclusive) — horizontal and vertical resolution and horizontal and vertical size of the screen you have to build, respectively. The next line contains a single integer number n (1 ≤ n ≤ 100)  — the number of different screen types available to you. The next n lines contain descriptions of the available screen types. Each description occupies one line and consists of five integer numbers — rh,i, rv,i, sh,i, sv,i, pi (all from 100 to 10\,000 inclusive), where first four numbers are horizontal and vertical resolution and horizontal and vertical size of i-th screen type, and pi is the price.

### Output file format

Write to the output file a single integer — the minimal price of the specified giant screen.

### Sample tests

No. Input file (giant.in) Output file (giant.out)
1
1024 1024 300 300
3
1024 768 295 270 200
1280 1024 365 301 250
1280 800 350 270 210
250
2
2400 2000 800 700
3
1024 768 295 270 200
1280 1024 365 301 250
1280 800 350 270 210
1260

## Problem H. Hell on the Markets ≡

 Author: ACM ICPC NEERC 2008 Jury | Roman Elizarov (original text), Georgiy Korneev (editing) Input file: hell.in Time limit: 2 sec Output file: hell.out Memory limit: 256 Mb

### Statement

Most financial institutions had become insolvent during financial crisis and went bankrupt or were bought by larger institutions, usually by banks. By the end of financial crisis of all the financial institutions only two banks still continue to operate. Financial markets had remained closed throughout the crisis and now regulators are gradually opening them. To prevent speculation and to gradually ramp up trading they will initially allow trading in only one financial instrument and the volume of trading will be limited to i contracts for i-th minute of market operation.

Two banks had decided to cooperate with the government to kick-start the market operation. The boards of directors had agreed on trading volume for each minute of this first trading session. One bank will be buying ai contracts (1 ≤ ai ≤ i) during i-th minute (1 ≤ i ≤ n), while the other one will be selling. They do not really care whether to buy or to sell, and the outside observer will only see the volume ai of contracts traded per minute. However, they do not want to take any extra risk and want to have no position in the contract by the end of the trading session. Thus, if we define bi = 1 when the first bank is buying and bi = −1 when the second one is buying (and the first one is selling), then the requirement for the trading session is that ni=1ai bi = 0.

Your lucky team of three still works in the data center (due to the crisis, banks now share the data center and its personnel) and your task is to find such bi or to report that this is impossible.

### Input file format

The first line of the input file contains the single integer number n (1 ≤ n ≤ 105).

The second line of the input file contains n integer numbers — ai (1 ≤ ai ≤ i).

### Output file format

The first line of the output file must contain "Yes" if the trading session with specified volumes is possible and "No" otherwise. In the former case the second line must contain n numbers — bi.

### Sample tests

No. Input file (hell.in) Output file (hell.out)
1
4
1 2 3 4
Yes
1 -1 -1 1
2
4
1 2 3 3
No

## Problem I. iSharp ≡

 Author: ACM ICPC NEERC 2008 Jury | Roman Elizarov Input file: isharp.in Time limit: 2 sec Output file: isharp.out Memory limit: 256 Mb

### Statement

You are developing a new fashionable language that is not quite unlike C, C++, and Java. Since your language should become an object of art and fashion, you call it i# (spelled i-sharp). This name combines all the modern naming trends and also hints at how smart you are.

Your language caters for a wide auditory of programmers and its type system includes arrays (denoted with "[]"), references (denoted with "&"), and pointers (denoted with "*"). Those type constructors can be freely combined in any order, so that a pointer to an array of references of references of integers (denoted with "int&&[]*") is a valid type.

Multiple variables in i# can be declared on a single line with a very convenient syntax where common type of variables is given first, followed by a list of variables, each optionally followed by additional variable-specific type constructors. For example, the following line:

int& a*[]&, b, c*;

declares variables a, b, and c with types int&&[]*, int&, and int&* correspondingly. Note, that type constructors on the right-hand sides of variables in i# bind to variable and their order is reversed when they are moved to the left-hand side next to type. Thus int*& a is equivalent to int a&*.

However, you discover that coding style with multiple variable declarations per line is confusing and is outlawed in many corporate coding standards. You decide to get rid of it and refactor all existing i# code to a single variable declaration per line and always specify type constructor next to the type it refers to (instead of the right-hand side of variable). Your task it to write such refactoring tool.

### Input file format

The input file contains a single line with a declaration of multiple variables in i#. The line starts with a type name, followed by zero, one, or more type constructors, followed by a space, followed by one or more variable descriptors separated by "," (comma) and space, and terminated by ";" (semicolon). Each variable descriptor contains variable name, followed by zero, one, or more type constructors.

Type name and variable names are distinct and consist of lowercase and uppercase English letters from a to z or A to Z. The line contains at most 120 characters and does not contain any extra spaces.

### Output file format

Write to the output file a line for each variable declared in the input file. For each variable write its declaration on a single line in the same format as in the input file, but with all type constructors next to its type. Separate type with all type constructors from a variable name by a single space. Do not write any extra spaces.

### Sample tests

No. Input file (isharp.in) Output file (isharp.out)
1
int&amp; a*[]&amp;, b, c*;
int&amp;&amp;[]* a;
int&amp; b;
int&amp;* c;
2
Double[][] Array[];
Double[][][] Array;

## Problem J. Javanese Cryptoanalysis ≡

 Author: ACM ICPC NEERC 2008 Jury | Mikhail Dvorkin Input file: javanese.in Time limit: 2 sec Output file: javanese.out Memory limit: 256 Mb

### Statement

Javanese is the language of the people in the Central and Eastern parts of the island of Java, Indonesia.

In 1926, a standard orthography using the English Alphabet was created for the Javanese language. This writing system uses all letters from A to Z. The five letters A, E, I, O, and U are vowels, while all other letters are consonants. In Javanese words vowels and consonants always alternate. This property is quite useful when deciphering encrypted Javanese texts.

A text s consists of words, each word contains only capital letters. Let's call text s legitimate if in each word of s vowels and consonants alternate (no two vowels and no two consonants are located next to each other).

A simple substitution cipher is applied to a text s. That is, a bijection f: A ↦ A is chosen, where A is the set of capital letters. The encoded text t is obtained from s by substituting each letter c with f(c).

You're given the encoded text t. Find any legitimate text s that can be encoded as t, or detect that there is no such legitimate s.

### Input file format

The input file contains the encoded text t, a list of words separated by spaces and/or line breaks. Each word consists only of capital letters (A to Z).

The input file contains no more than 105 characters.

### Output file format

If the text t cannot be an encoded legitimate text, output only one word "impossible".

Otherwise, output any legitimate text s that can be encoded into t. Separate words of s with spaces and/or line breaks. All letters in s should be capital.

### Sample tests

No. Input file (javanese.in) Output file (javanese.out)
1
O RISK LIP FOCUS LUCKY
A CODE FOR VALID FILES
2
NEERC
impossible

## Problem K. KINA Is Not Abbreviation ≡

 Author: ACM ICPC NEERC 2008 Jury | Georgiy Korneev (idea and original text), Mikhail Dvorkin (final text) Input file: kina.in Time limit: 2 sec Output file: kina.out Memory limit: 256 Mb

### Statement

When introducing new terms consisting of several words, it is useful to use abbreviations. An abbreviation is a word that consists of the first letters of several consecutive words.

An abbreviation is called unambiguous if the following two conditions are satisfied:

• It corresponds to exactly one sequence of words in a given text (although this sequence can appear in the text more than once);
• It does not appear in the text by itself.

For example, in the text "A recursive acronym KINA means "KINA is not abbreviation", strings "ARA" and "K" are unambiguous abbreviations, strings "A" and "KINA" are ambiguous abbreviations, and strings "RAA" and "KNA" are not abbreviations.

To introduce an abbreviation in a text, it is placed in parentheses right after the sequence of words it corresponds to. Future occurrences of this sequence of words can be replaced by the abbreviation. In the example text above, introduction of the abbreviation "K" produces the following text: "A recursive acronym KINA (K) means "K is not abbreviation"".

If two occurrences of a sequence of words overlap, only one of them can be replaced by the abbreviation. Words in a sequence are separated by one or more non-alphabetic characters. Comparison of words is case-insensitive. For example, "i18n" is an occurrence of the word sequence "I n".

The effectiveness of an abbreviation is the decrease in the number of letters after introduction of this abbreviation. Only letters are taken into account; spaces, parentheses and all other non-alphabetical characters do not count.

Given a text, find an unambiguous abbreviation with the maximum effectiveness.

### Input file format

The input file contains a text with at most 4000 characters. The text contains only characters with ASCII codes 32 (space) to 126 ("~"), 13 (carriage return), and 10 (line feed).

### Output file format

If there is no unambiguous abbreviation with positive effectiveness, then the output file should contain the single number 0.

Otherwise, the first line of the output file should contain the effectiveness of the optimal abbreviation. The second line should contain the unambiguous abbreviation itself. If there are multiple unambiguous abbreviations with the maximum effectiveness, output any one of them.

### Sample tests

No. Input file (kina.in) Output file (kina.out)
1
This problem name is "KINA is not abbreviation".
Once again: KINA is not abbreviation.
11
NA
2
To be or not to be: that is the question.
0
3
Here is the chorus of the song "Jingle Bells":
Jingle bells, jingle bells,
Jingle all the way;
Oh what fun it is to ride
In a one-horse open sleigh.
16
JB

0.145s 0.005s 35