Interval cíclic P72067

Statement

Teniu $n$ nombres enters $a_1, \dots, a_n$ . Els col·loqueu mantenint l’ordre en sentit horari en una circumferència, de manera que a la dreta de cada $a_k$ està $a_{k+1}$ , excepte per a $a_n$ , que a la dreta té $a_1$ .

Donada una $s$ , és possible trobar un interval de nombres consecutius que sumi $s$ ?

Entrada

L’entrada conté diversos casos, cadascun amb $s$ , $n$ i els $n$ nombres $a_1$ , …, $a_n$ . Podeu suposar $-10^{14} \le s \le 10^{14}$ , $1 \le n \le 10^5$ , i $-10^9 \le a_k \le 10^9$ .

Sortida

Escriviu una línia per a cada cas. Si no hi ha cap interval que sumi $s$ , escriviu “NO”. Altrament, escriviu "SI", seguit de l’inici i del final de l’interval, que ha de tenir entre 1 i $n$ elements. Si hi ha més d’una solució, trieu la que vulgueu, però seguiu estrictament el format dels exemples.

Puntuació

Cas A:

Casos on $0 \le s \le 10^{14}$ i $0 \le a_k \le 10^9$ , com l’exemple d’entrada 1.

Cas B:

Resta de casos.

Public test cases

Input

7  4  1 2 3 4
7  4  1 2 3 4
23  1  23
0  3  42 42 42
168  3  42 42 42
3000000000  3  1000000000 1000000000 1000000000

Output

SI 4 2
SI 3 4
SI 1 1
NO
NO
SI 2 1

Input

-3  4  -1 8 9 -2
2  5  1 -1 -1 -1 1
-3000000000  3  -1000000000 -1000000000 -1000000000
-23  4  -10 20 -30 42
3  2  9 -6
-3  2  -2 -3
23  10  8 3 4 -1 4 0 4 -7 4 -3

Output

SI 4 1
SI 5 1
SI 2 1
NO
SI 2 1
SI 2 2
SI 9 7

Information

Author: Xavier Povill
Language: Catalan
Official solutions: C++ Python
User solutions: C++