Dados los números enteros no negativos ~P~ y ~B~ donde ~P~ es primo, y ~1 \le B \le P-1~. Para una secuencia de números enteros no negativos ~X = (x_1,x_2,...,x_n)~, el valor hash, ~hash(X)~ se define de la siguiente manera: $$\displaystyle hash(X) = \left(\sum_{i=1}^n x_i B^{n-i}\right) \mod P $$ Se te dan ~M~ pares de números enteros ~(L_1, R_1), (L_2, R_2),...,(L_M, R_M)~. La tarea es determinar si existe una secuencia de números enteros no negativos ~A = (A_1,A_2,...,A_N)~ de longitud ~N~ que cumpla la siguiente condición: Para todo ~i~ ~(1 \le i \le M)~, se cumple la siguiente condición: sea ~s~ la secuencia ~(A_{L_i}, A_{L_i+1},...,A_{R_i})~ obtenida tomando los elementos del ~L_i~-ésimo al ~R_i~-ésimo de ~A~. Entonces, ~hash(s) \neq 0~.

Entrada

Los datos se leerán desde la entrada estándar en el siguiente formato:

P B N M  
L1 R1  
L2 R2   
…  
LM RM

Salida

Su programa debe escribir en una sola línea Yes si existe tal secuencia o No en caso contrario.

Restricciones

• ~2 \le P \le 10^9~
• ~P~ es primo.
• ~1 \le B \le P-1~
• ~1 \le N \le 16~
• ~1 \le M \le N(N+1)/2~
• ~1 \le L_i \le R_i \le N~
• ~(L_i, R_i) \neq (L_j, R_j)~ si ~i \neq j~.

Ejemplo #1 de Entrada

3 2 3 3
1 1
1 2
2 3

Ejemplo #1 de Salida

Yes

Ejemplo #2 de Entrada

2 1 3 3
1 1
2 3
1 3

Ejemplo #2 de Salida

No

Ejemplo #3 de Entrada

998244353 986061415 6 11
1 5
2 2
2 5
2 6
3 4
3 5
3 6
4 4
4 5
4 6
5 6

Ejemplo #3 de Salida

Yes