Nosaukums
Līdzsvarota virkne (lidzsvirkne)
Laika limits
1.00s
Atmiņas limits
64.0 MB
Grūtība
47%

Definīcija

Miķelis uz tāfeles uzrakstīja n veselu skaitļu virkni a1, a2, ..., an. Viņš nosauca savu virkni par līdzsvarotu, jo katrs skaitlis bija vienāds ar blakusesošo skaitļu summu. Precīzāk,

a1 = a2, 
a2 = a1 + a3, 
a3 = a2 + a4, 
... 
an - 1 = an - 2 + an,
an - 1 = an.

Piemēram, virkne, kas sastāv no visām 0, ir līdzsvarota.

Kāmēr Miķelis aizgāja pēc piparkūkām, Anniņa nodzēsa dažus skaitļus no tāfeles, jo Miķelis nepalīdzēja viņai ar mājasdarbu. Miķelis sabozās un izlēma padalīties ar piparkūkām tikai tad, ja Anniņa atjaunos viņa virkni.

Palīdzi Miķelim un Anniņai salīgt un atjauno līdzsvarotu virkni, vai arī nosaki, ka tas vai nu nav izdarāms viennozīmīgi, vai nu vispār nav iespējams!

Ievaddatu raksturojums

Pirmajā rindā doti divi veseli skaitļi n un m. Ar n tiek apzīmēts skaitļu skaits virknē (2 ≤ n ≤ 105). Skaitlis m apzīmē nenodzēstu skaitļu skaitu (0 ≤ m ≤ n). Tālāk seko m rindas, kas katra satur divus skaitļus i un x, kas nozīmē, ka ai = x (1 ≤ i ≤ n,  - 109 ≤ x ≤ 109).

Garantēts, ka ievaddati nav pretrunīgi.

Izvaddatu raksturojums

Ja līdzsvarotu virkni var atjaunot tieši vienā veidā, pirmajā rindā izvadi vārdu "MIERS". Nākamajā rindā izvadi n skaitļus a1, a2, ..., an, atdalītus ar atstarpēm.

Ja virkni vairs nevar atjaunot viennozīmīgi, vienīgajā rindā izvadi vārdu "STRIDS".

Ja nu Miķelis bija kļūdījies un jau sākumā virkne nebija līdzsvarota, vienīgajā rindā izvadi vārdu "PARPRATUMS".

Paraugdati

Stdin
2 1
1 5
Stdout
MIERS
5 5
Stdin
5 0
Stdout
STRIDS
Stdin
2 2
1 2
2 3
Stdout
PARPRATUMS

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.