zudt

Se consideră un număr natural $N$ și un șir $A = (a_1, a_2, a_3, \dots, a_N)$ format din $N$ numere naturale nenule.

Definim $S(i, j)$ ca fiind egal cu suma $a_i + a_{i+1} + a_{i+2} + \dots + a_j$, unde $1 \le i \le j \le N$.

Cerință

Se cunosc numărul $N$ și șirul $A$. Scrieți un program care să determine răspunsurile pentru următoarele trei întrebări:

1. Există o poziție $i$ ($1 \le i < N$) cu proprietatea că $S(1, i) = S(i + 1, N)$?
2. Există o poziție $i$ ($1 < i < N$) cu proprietatea că $S(1, i - 1) = S(i + 1, N)$?
3. Există două poziții $i$ și $j$ ($1 < i$ și $i + 1 < j < N$) cu proprietatea că $S(1, i - 1) = S(i + 1, j - 1) = S(j + 1, N)$?

Date de intrare

Fișierul de intrare zudt.in conține:

• pe prima linie, un număr natural $C$ ($1$, $2$ sau $3$), reprezentând cerința care trebuie rezolvată;
• pe a doua linie, numărul natural $N$ cu semnificația din enunț;
• pe a treia linie, $N$ numere naturale nenule, separate prin câte un spațiu, reprezentând elementele șirului $A$.

Date de ieșire

Fișierul de ieșire zudt.out conține pe prima linie răspunsul determinat pentru cerința $C$:

• Pentru $C = 1$, prima linie conține un număr natural reprezentând răspunsul la prima întrebare. Dacă există o astfel de poziție $i$ astfel încât $S(1, i) = S(i + 1, N)$, atunci răspunsul este numărul $i$. Dacă nu există, atunci răspunsul este numărul $0$;
• Pentru $C = 2$, prima linie conține un număr natural reprezentând răspunsul la a doua întrebare. Dacă există o astfel de poziție $i$ astfel încât $S(1, i - 1) = S(i + 1, N)$, atunci răspunsul este numărul $i$. Dacă nu există, atunci răspunsul este numărul $0$;
• Pentru $C = 3$, prima linie conține două numere naturale, separate printr-un singur spațiu, reprezentând răspunsul la a treia întrebare. Dacă există două poziții distincte $i$ și $j$ astfel încât $S(1, i - 1) = S(i + 1, j - 1) = S(j + 1, N)$, atunci răspunsul este format din numărul $i$ și numărul $j$, în această ordine. Dacă nu există, atunci răspunsul este numărul $0$.

Restricții și precizări

• $C \in \{1, 2, 3\}$;
• $5 \le N \le 200 \ 000$;
• $1 \le a_i \le 1 \ 000$, $i = 1, 2, \dots, N$;
• $S(i, i) = a_i$, $i = 1, 2, \dots, N$.

Exemplul 1

zudt.in

1
9
2 3 1 4 2 4 4 5 15

zudt.out

7

Explicație

$i = 7$, deoarece $S(1, 7) = 20$ și $S(8, 9) = 20$.

Exemplul 2

zudt.in

1
5
2 3 1 4 6

zudt.out

0

Explicație

Nu există o poziție $i$ cu proprietatea cerută:
$S(1, 1) = 2$, $S(2, 5) = 14$, $2 \ne 14$;
$S(1, 2) = 5$, $S(3, 5) = 13$, $5 \ne 13$;
$S(1, 3) = 6$, $S(4, 5) = 10$, $6 \ne 10$;
$S(1, 4) = 10$, $S(5, 5) = 6$, $10 \ne 6$.

Exemplul 3

zudt.in

2
5
2 3 1 4 2

zudt.out

0

Explicație

Nu există o poziție $i$ cu proprietatea cerută:
$i = 2$, $S(1, 1) = 2$, $S(3, 5) = 7$, $2 \ne 7$;
$i = 3$, $S(1, 2) = 5$, $S(4, 5) = 6$, $5 \ne 6$;
$i = 4$, $S(1, 3) = 6$, $S(5, 5) = 2$, $6 \ne 2$.

Exemplul 4

zudt.in

2
9
2 3 1 4 202 7 1 1 1

zudt.out

5

Explicație

$i = 5$, deoarece $S(1, 4) = 10$ și $S(6, 9) = 10$.

Exemplul 5

zudt.in

3
9
2 3 1 8 6 7 2 2 2

zudt.out

4 6

Explicație

$i = 4$ și $j = 6$, deoarece $S(1, 3) = 6$, $S(5, 5) = 6$ și $S(7, 9) = 6$.