Problem A. Second Best ≡

Author:A. Klenin
Input file: input.txt   Time limit:2 sec
Output file: output.txt   Memory limit:4 Mb

Statement

Given the sequence of integers A1, A2, …, AN, find a number As such that there exists exactly one Am > As, and for all k ≠ m Ak ≤ As.

Input file format

Input contains N followed by A1 A2… AN.

Output file format

Output should contain a single integer — As, or −1 if no such number exists.

Constraints

1 ≤ N ≤ 1000000, 0 ≤ Ai ≤ 109,

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
3
1 2 3
 
2
2 
4
3 3 2 3
 
-1

Problem B. Repeating digit (easy) ≡

Author:T. Chistyakov, A. Klenin
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:256 Mb

Statement

For given integers P and N you need to find all such values of x < 10N, that N last digits of xP are non-zero and equal.

Fortunately, there is not so many numbers showing this property. For example, for P = 2 and N = 2 there exist only 4 of them:

12, 38, 62, 88

Input file format

Input file contains P and N.

Output file format

Output the number of existing numbers X, then all these numbers in any order.

Constraints

2 ≤ P ≤ 100

2 ≤ N ≤ 9

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
3 2

8 
14 42 53 64 77 71 92 99

Problem C. Uncertain Finish ≡

Author:T.Chistyakov, A. Klenin
Input file: input.txt   Time limit:2 sec
Output file: output.txt   Memory limit:32 Mb

Statement

At the running contest, jury used a new computerized stopwatch system to ensure the most accurate measuring of results. Unfortunately, despite very successfull trials, the system malfunctioned during the actual contest.

Jury was so confident in the new system that it did not use the old mechanical stopwatches. So the only way to determine outcome was to compare visual impressions of the people watching the contest. M such impressions were recorded, each in one of two forms: "runner A finished before runner B" and "runners A and B finished at the same time".

You task is to assign a place pi to each of N runners, such that

  1. If there is a record that A and B finished at the same time, then pA = pB.
  2. If there is a record that A finished before B, then pA < pB.

Additionally, places must be allocated as densely as possible, i.e. 1 ≤ pi ≤ K for minimum possible value of K.

Input file format

Input file contains integers N M followed by M pairs Ai Bi ci, where ci = 0 means the record "runners Ai and Bi finished at the same time", ci = 1 means the record "runner Ai finished before Bi".

Output file format

Output file must contain either a single number −1, if the places could not be assigned, or a sequence of N numbers pi. If several solutions exist, output any of them.

Constraints

1 ≤ N ≤ 10000, 0 ≤ M ≤ 106, 1 ≤ Ai, Bi ≤ N

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
3 2
3 2 1
2 1 0
 
2 2 1
0.032s 0.005s 11