Author:  ACM ICPC 20092010, NEERC, Northern Subregional Contest  
Input file:  auxiliary.in  Time limit:  3 sec  
Output file:  auxiliary.out  Memory limit:  256 Mb 
As you probably know, scientists already discovered the Ultimate question of life, the Universe, and everything, and it is ``What do you get if you multiply six by nine?''. Not satisfied by this, the scientists contracted a small Magrateyan company to construct a minicomputer to find out some more specific question (they named it auxiliary), which can theoretically shed more light on life, the Universe or something else.
This computer was built, but unluckily (although not unexpectedly) the result of computation was corrupted and partially lost. Finally the computer constructors managed to receive a string, which is a part of the correct question. After thorough analysis the constructors started to believe that the original result can be reconstructed from the string by adding some letters to it without the string letters being reordered or removed. Also they believe that the correct result is an arithmetic expression (as with the Ultimate question), but since the question is auxiliary, it contains no multiplication, only addition. More precisely, it should correspond to the depicted grammar.
They need your help to give just something to their clients. They ask you to reconstruct the question based on the corrupted computer answer which they managed to retrieve.
No.  Input file (auxiliary.in ) 
Output file (auxiliary.out ) 

1 


2 


3 


Author:  ACM ICPC 20092010, NEERC, Northern Subregional Contest  
Input file:  bureau.in  Time limit:  3 sec  
Output file:  bureau.out  Memory limit:  256 Mb 
Long ago, in a kingdom far, far away the king decided to keep a record of all laws of his kingdom. From that moment whenever a new law was passed, a corresponding record was added to the law archive.
Many centuries later lawyers discovered that there were only two types of laws in the kingdom:
The law is considered active if and only if there is no active law that cancels it.
You are to write program that finds out which laws are still active.
The first line of the input file contains an integer number n (1 ≤ n≤ 10^{5}) — the number of passed laws.
The following n lines describe one law each. Each description has one of the following formats:
The laws are numbered from one.
No.  Input file (bureau.in ) 
Output file (bureau.out ) 

1 


Author:  ACM ICPC 20092010, NEERC, Northern Subregional Contest  
Input file:  circles.in  Time limit:  3 sec  
Output file:  circles.out  Memory limit:  256 Mb 
Yesterday Andrew wrote a program that draws n white circles on a black screen. The screen is monochrome and it has a resolution w × h pixels. Pixels are numbered from upper left corner (0, 0) to bottom right one (w−1, h−1).
A circle with the center at pixel (x_{c}, y_{c}) and the radius r consists of the pixels with coordinates (x, y) such that √(x_{c} − x)^{2} + (y_{c} − y)^{2} ≤ r. If the circle does not fit on the screen, it is truncated. If some pixel belongs to two or more circles, it is white.
The resulting picture was very nice, so Andrew decided to copy it to his wall. He has white wallpaper and he can only draw some parts of wall into black. Now he wants to know the amount of paint he needs. He copies the picture exactly pixeltopixel, so you should write a program that calculates the number of black pixels left on a screen after drawing n circles.
In the first line of input file there are three integers: w, h, and n (1 ≤ w, h ≤ 20000; 1 ≤ n ≤ 100). Each of the following n lines contains descriptions of the circle. In i+1th line there are three integers: x_{i}, y_{i}, r_{i} (0 ≤ x_{i} < w; 0 ≤ y_{i} < h; 0 ≤ r_{i} ≤ 40 000). They denote a circle with the center at pixel (x_{i}, y_{i}) and radius r_{i}.
Note: The picture corresponds to the second example.
You should output exactly one number — the number of black pixels left on the screen.
No.  Input file (circles.in ) 
Output file (circles.out ) 

1 


2 


Author:  ACM ICPC 20092010, NEERC, Northern Subregional Contest  
Input file:  dragon.in  Time limit:  3 sec  
Output file:  dragon.out  Memory limit:  256 Mb 
In a land faraway there lives a noble man, and he has three sons. The elder of them is very clever, his especial strength is calculation: he can easily count a determinant of fifth degree in his mind without paper and pencil. The middle brother is also very talented, he is particularly strong in theoretic questions. But the younger brother has absolutely no talent in mathematics.
One day they went for a walk. Suddenly a wind started to blow and something closed the sun from them: it was a hungry dragon, returning to his lair from unsuccessful hunt.
``Hey, boys. I will give you a problem, and if you do not solve it, nothing will save you!'' — said the dragon.
The elder brothers smiled ironically. Of course, they were so clever that no dragon could ask them a question they were not able to answer.
``Give me a positive integer number which is divisible by d and has exactly n digits in it, assuming that d is equal to fortyfive and n is equal to three!'' — was the dragon's question.
``One hundred and thirtyfive.'' — answered the elder brother.
``Good, go where you want. But I will return and ask you a similar question in a year.'' — said the upset hungry dragon and flew away.
A year passed, and the elder brother got married and left his parents' home. Two younger brothers went for a walk discussing this event, and met the dragon again.
``Hey boys, give me a positive integer number which is divisible by twenty three and has exactly one digit in it'' — asked the dragon.
``No solution'' — answered the middle brother.
``You are still too clever, go where you want. But I will return and ask you a similar question.'' — said the dragon and flew away.
Another year passed and the middle brother got married and left his parents' home. The younger brother now does not go outside, because he does not have enough knowledge to answer the dragon's questions. Please, help him and write a program — the boy is very afraid.
The input file contains the only line with numbers n and d (1 ≤ n ≤ 1000; 1 ≤ d ≤ 1 000 000).
The first and only line of the output file must contain the answer to be given to the dragon — either a ndigit number (without leading zeroes) divisible by d or a string "No solution".
No.  Input file (dragon.in ) 
Output file (dragon.out ) 

1 


2 


3 


Author:  ACM ICPC 20092010, NEERC, Northern Subregional Contest  
Input file:  enigmatic.in  Time limit:  3 sec  
Output file:  enigmatic.out  Memory limit:  256 Mb 
Yes, it happened! The first contact! Aliens will visit the Earth in 2010! And they promised to bring an enigmatic device which cannot be constructed using existing Earth technologies. Most of the scientists of the world think so! All newspapers already published their leading articles about it.
This device will accept an integer sequence {a_{i}} as its initial input. After that, it can perform the following two operations:
The amazing thing about this device is that it is able to perform 50 000 operations of this kind with a sequence of 50 000 numbers within 3 seconds. Nobody could do it before!
But Roman does not believe in aliens and thinks that it is only a great hoax made by somebody just to win another million bucks on the stock exchange. His goal is to prove this. So he hired you to write a program to simulate this device.
Given an integer sequence a_{i} and a sequence of operations, write a program which simulates the behaviour of the strange alien device.
The first line of the input contains the length of the sequence n (1≤ n≤ 50 000). The second line contains n numbers a_{i} forming the initial sequence (0≤ a_{i}≤ 2009). The third line contains the number of operations m (1≤ m≤ 50 000). The rest of file contains m lines, each describing one operation. The jth operation is described by its kind k_{j} ("1" for squaring, "2" for calculating the sum), followed by two integers l_{j} and r_{j} (1≤ l_{j} ≤ r_{j}≤ n).
For each operation of the second kind, write their output on the separate line, in order they appear in the input.
No.  Input file (enigmatic.in ) 
Output file (enigmatic.out ) 

1 


Author:  ACM ICPC 20092010, NEERC, Northern Subregional Contest  
Input file:  four.in  Time limit:  3 sec  
Output file:  four.out  Memory limit:  256 Mb 
Mike is a magician. One of his inventions is a labyrinth that gives supernatural abilities to every person who walks through it. The labyrinth has an extremely complicated internal structure, however, for an external observer it is just a square on the ground.
Mike has found some suitable place for labyrinth on the seashore. He drew its border on the sand and marked four points with small stones so that each side of the square contained exactly one stone and no stone was placed in the corner.
As no picture drawn on the sand stays forever, after a while Mike found only the stones on their places. Now he wonders where the marked square could have been.
Your task is to restore some possible place of the labyrinth and return four corners of the square as a result. You may assume that the seashore is a plane and the stones are points on it.
The first four lines of the input file contain two integer numbers x_{i} and y_{i} each — coordinates of the ith point (−1 000 ≤ x_{i}, y_{i} ≤ 1 000). No two points coincide, no three points are collinear.
Output four lines containing two real numbers each — coordinates of the vertices of the square. Vertices should be listed in either clockwise or counterclockwise order. Coordinates must be precise up to 6 digits after the decimal point.
If there are multiple solutions, output any of them. If there is no solution, write four pairs of zeroes instead of the coordinates.
No.  Input file (four.in ) 
Output file (four.out ) 

1 


2 


Author:  ACM ICPC 20092010, NEERC, Northern Subregional Contest  
Input file:  gtaw.in  Time limit:  3 sec  
Output file:  gtaw.out  Memory limit:  256 Mb 
Tommy is a wheel thief. His job was formerly as easy as pie: you lift a car, turn off wheel bolts, take the wheel and run away. But now everybody uses "antitheft" bolts.
Antitheft bolt is designed in such a way that it cannot be turned off with a usual wrench. Its head is a cylinder with a hole. To turn the antitheft bolt off you need a right wrench. The wrench has a ring with a lug that exactly matches the shape of the bolt head.
Of course Tommy cannot get wrenches for all possible antitheft bolts. But sometimes it is possible to turn off the bolt with the wrench that does not match it exactly.
More formally, the wrench can turn off the bolt if and only if two following conditions are satisfied:
Due to technical reasons, the shape of both — hole of the bolt head and lug of the wrench, are always a starshaped polygons with theirs centers in the center of the bolt or wrench. So if it is described in polar coordinate system as a sequence of pairs (r_{i}, φ_{i}) then φ_{i + 1} < φ_{i} and φ_{i + 1} − φ_{i} < 180^{∘}.
Help Tommy do find out if it is possible to turn off the bolt with the wrenches he has.
The first line of input file contains two integer numbers n and r — the number of wrenches and the radii of the bolt head and the wrenches' rings (1≤ n≤ 10, 1≤ R≤ 1000).
The following lines describe the bolt head. Description consists of an integer number m — number of vertices (3≤ m≤ 100) and m pairs of integer numbers (r_{i}, φ_{i}) (1≤ r_{i} < R; 0^{∘ }≤ φ_{i} < 360^{∘}; φ_{i} < φ_{i+1}; φ_{i+1} − φ_{i} < 180^{∘}; φ_{m} − φ_{1} > 180^{∘}).
The rest lines describe the wrenches in the same format.
The first line of the output file must contain the number of wrenches that can be used to turn off the bolt. The following lines must contain wrench numbers in increasing order.
No.  Input file (gtaw.in ) 
Output file (gtaw.out ) 

1 


Author:  ACM ICPC 20092010, NEERC, Northern Subregional Contest  
Input file:  homo.in  Time limit:  3 sec  
Output file:  homo.out  Memory limit:  256 Mb 
Consider a list of numbers with two operations:
For example: the result of the insertion of a number 4 to the list [1, 2, 1] is the list [1, 2, 1, 4]. If we delete the number 1 from this list, we get the list [2, 1, 4], but if we delete the number 3 from the list [1, 2, 1, 4], the list stays unchanged.
The list is homogeneous if it contains at least two equal numbers and the list is heterogeneous if it contains at least two different numbers. For example: the list [2, 2] is homogeneous, the list [2, 1, 4] is heterogeneous, the list [1, 2, 1, 4] is both, and the empty list is neither homogeneous nor heterogeneous.
Write a program that handles a number of the operations insert and delete on the empty list and determines list's homogeneity and heterogeneity after each operation.
The first line of the input file contains an integer number n — the number of operations to handle (1 ≤ n ≤ 100 000).
Following n lines contain one operation description each. The operation description consists of a word insert or delete, followed by an integer number k — the operation argument (−10^{9} ≤ k ≤ 10^{9}).
For each operation output a line, containing a single word, describing the state of the list after the operation:
No.  Input file (homo.in ) 
Output file (homo.out ) 

1 


Author:  ACM ICPC 20092010, NEERC, Northern Subregional Contest  
Input file:  image.in  Time limit:  3 sec  
Output file:  image.out  Memory limit:  256 Mb 
Irene works for Novel Efforts in Effective Recognition of Characters (NEERC). Her new project concerns image recognition using robots.
Since the approach is quite innovative, Irene starts with a very simple model first. She fixed d~images which are called digits 0 to d − 1. Each image is a w × h rectangle filled with white and black unit squares (call them pixels). All images are distinct (that is, each two images differ in at least one pixel).
The robot is placed in the upper left pixel of one of the images. It starts executing a program written in a specific programming language described below. The task of the robot is to recognize which of the d~images it was placed onto.
The programming language for the robot consists of the following commands:
Each movement command takes one time unit to execute. The execution of conditional operator and image recognized commands is instantaneous.
Irene is interested in the program that always works correctly. That is, if a robot is placed onto the image corresponding to the digit i, then the execution of the program must end with the command i.
Given the set of images, design a correct program for the robot, such that its execution time in the worst case is minimal.
The first line contains three integers d, h, and w (1 ≤ d ≤ 10; 1 ≤ h, w ≤ 10) — the number of considered images, the height and the width of each image.
The rest if the input file contains d descriptions of images. Each description consists of h lines of length w. All characters are either B or W, representing a black or a white pixel respectively.
Image descriptions are given in the order from 0 to d − 1. Descriptions are separated by an empty line.
Return a correct program for the robot with minimal possible worstcase execution time. If there are multiple possible programs, output any of them.
All whitespace is ignored when parsing a program.
No.  Input file (image.in ) 
Output file (image.out ) 

1 


Author:  ACM ICPC 20092010, NEERC, Northern Subregional Contest  
Input file:  jealous.in  Time limit:  3 sec  
Output file:  jealous.out  Memory limit:  256 Mb 
There is a trouble in Numberland, prime number p is jealous of another prime number q. She thinks that there are more integer numbers between a and b, inclusively, that are divisible by greater power of q than that of p. Help p to get rid of her feelings.
Let α(n, x) be maximal k such that n is divisible by x^{k}. Let us say that a number n is pdominating over q if α(n, p)>α(n, q). Find out for how many numbers between a and b, inclusive are pdominating over q.
The first line of the input file contains a, b, p and q (1 ≤ a ≤ b ≤ 10^{18}; 2 ≤ p, q ≤ 10^{9}; p ≠ q; p and q are prime).
In the given example 3, 9, 15 and 18 are 3dominating over 2.
Output one number — how many numbers n between a and b, inclusive, are pdominating over q.
No.  Input file (jealous.in ) 
Output file (jealous.out ) 

1 


Author:  ACM ICPC 20092010, NEERC, Northern Subregional Contest  
Input file:  kripke.in  Time limit:  3 sec  
Output file:  kripke.out  Memory limit:  256 Mb 
Testing and quality assurance are very timeconsuming stages of software development process. Different techniques are used to reduce cost and time consumed by these stages. One of such techniques is software verification. Model checking is an approach to the software verification based on Kripke models.
A Kripke model is a 5tuple (AP, S, S_{0}, R, L), where AP is a finite set of atomic propositions, S is a finite set of model's states, S_{0} ⊂ S is a set of initial states, R ⊂ S × S is a transition relation, and L ⊂ S × AP is a truth relation. In this problem we will not take initial states into account and relation R will be a reflexive relation, so R(s, s) will be true for all states s ∈ S.
A path π beginning in state s in the Kripke model is an infinite sequence of states s_{0} s_{1}… such that s_{0}=s, and for each i ≥ 0 the (s_{i}, s_{i+1}) ∈ R.
Temporal logic and its subset Computational tree logic (CTL) are used to describe propositions qualified in terms of time. Kripke models are often used to check properties, described in CTL.
There are two types of formulae in CTL: state formulae and path formulae. The values of state and path formulae are evaluated for states and paths correspondingly.
If p ∈ AP then p is a state formula that holds in state s iff (s, p) ∈ L.
If f is a path formula, then A f and E f are state formulae, where A and E are path quantifiers:
If f and g are state formulae, then G f and fU g are path formulae, where G and U are temporal operators:
To verify a property described by a state formula f means to find all states, f holds for. Verification of an arbitrary property is a pretty complex problem. Your problem is much easier — you are to write a program that verifies a property described by a temporal logic formula E (x U(A G y)), where x and y are some atomic propositions.
The first line of the input file contains three positive integer numbers n, m and k — number of states, transitions and atomic propositions (1 ≤ n ≤ 10 000; 0 ≤ m ≤ 100 000; 1 ≤ k ≤ 26).
The following n lines describe one state each. The state i (1 ≤ i ≤ n) is described by c_{i} — a number of atomic propositions which are true for this state and a spaceseparated list of these atomic propositions (0 ≤ c_{i} ≤ k). Atomic propositions are denoted by first k small English letters.
The last line of the input file contains the formula of the property to be verified. This formula always has the form E(xU(AGy)), where "x" and "y" are some atomic propositions.
The first line of the output file must contain the number of states for which the verified property holds. The following lines must contain the numbers of these states listed in increasing order.
No.  Input file (kripke.in ) 
Output file (kripke.out ) 

1 

