Se consideră un număr natural N și un șir A=(a[1], a[2], a[3], ..., 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] + ... + a[j], unde 1 ≤ i ≤ j ≤ N.

Cerința

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 ≤ 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, conține 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 va 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 intrebare. 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 intrebare. 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 intrebare. 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 ∈ {1, 2, 3}
• 5 ≤ N ≤ 200.000
• 1 ≤ a[i] ≤ 1000, i = 1, 2, ..., N
• S(i,i) = a[i], i = 1, 2, ..., N
• Pentru 60 de puncte, C = 1 și N ≤ 1000
• Pentru 20 de puncte, C = 2 și N ≤ 200.000
• Pentru 20 de puncte, C = 3 și N ≤ 200.000

Exemplul 1:

zudt.in

1
9
2 3 1 4 2 4 4 5 15

zudt.out

7

Explicație

i = 7, 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 ≠ 14
S(1,2)=3, S(3,5)=13, 3 ≠ 13
S(1,3)=6, S(4,5)=10, 6 ≠ 10
S(1,4)=10, S(5,5)=6, 10 ≠ 5

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 ≠ 7
i=3, S(1,2)=5, S(4,5)=6, 5 ≠ 6
i=4, S(1,3)=6, S(5,5)=2, 6 ≠ 2

Exemplul 4:

zudt.in

2
9
2 3 1 4 202 7 1 1 1

zudt.out

5

Explicație

i=5, 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, S(1,3) = 6, S(5,5) = 6 și S(7,9) = 6