Tenemos una matriz triangular con ~n~ líneas, con números enteros. En esta matriz podemos construir una ruta usando la siguiente regla:

• el primer elemento de la ruta es el elemento ~a_{1,1}~.
• si el elemento ~a_{i, j}~ pertenece a la ruta, entonces el siguiente elemento de la ruta puede ser solo ~a_{i + 1, j}~ o ~a_{i + 1, j + 1}~, para cualquier ~1 \le j \le i < n~.

La ruta se codificará con números en el orden de la columna, pasando desde las líneas ~1~ a ~N~. El valor de la ruta es igual a la suma de los elementos que la conforman.

La ruta resaltada en el gráfico de ejemplo tiene el valor de ~5 + 4 + 6 + 5 + 4 = 24~, y está codificada por ~1,2,3,3,4~.

Ya sea el conjunto de todas las rutas máximas generadas en orden lexicográfico y numerado. Para el siguiente ejemplo, tenemos seis trayectorias de longitud máxima:

~Ruta~ ~1~. ~1 1 1 1 2 (5 + 2 + 7 + 6 + 4 = 24)~

~Ruta~ ~2~. ~1 1 1 2 2 (5 + 2 + 7 + 6 + 4 = 24)~

~Ruta~ ~3~. ~1 2 2 2 2 (5 + 4 + 5 + 6 + 4 = 24)~

~Ruta~ ~4~. ~1 2 3 3 4 (5 + 4 + 6 + 5 + 4 = 24)~

~Ruta~ ~5~. ~1 2 3 4 4 (5 + 4 + 6 + 5 + 4 = 24)~

~Ruta~ ~6~. ~1 2 3 4 5 (5 + 4 + 6 + 5 + 4 = 24)~

Tarea

Al conocer el tamaño y los elementos de una matriz triangular y respectivamente dos números naturales ~st~ y ~dr~ ~(st \le dr)~, se requiere determinar:

1. Número total de rutas máximas. Si este valor excede ~2000000000~, se imprimirá el valor de ~2000000001~.

2. Rutas con los números de serie ~st, st + 1, ..., dr~.

Entrada

La entrada contiene un número natural ~v~ en la primera línea. Para todas las pruebas de entrada, ~v~ solo puede tener un valor de ~1~ o ~2~.

La segunda línea contiene tres números naturales ~n~, ~st~ y ~dr~, separados por espacios. Las siguientes ~n~ líneas contienen una línea de la matriz triangular de la siguiente manera: la línea contiene ~i~ elementos, de la forma, ~a_{i, 1}~, ~a_{i, 2}~ ... ~a_{i, i}~, para cualquier ~1 \le i \le n~.

Salida

Si el valor de ~v~ es ~1~, solo se resolverá el punto ~1~ de la tarea. En este caso, en la salida se escribirá un solo número natural que representa el número de rutas de longitud máxima.

Si el valor de ~v~ es ~2~, solo se resolverá el punto ~2~ de la tarea. En este caso, en la salida se imprimirá en una línea, ~n~ números naturales separados por espacios, que representan la codificación de las rutas de valor máximo con ~st, st + 1, ..., dr~.

Restricciones y aclaraciones.

• ~1 \le n \le 2000~

• ~1 \le st \le dr \le 2 000 000 000~

• 1 ≤ dr - st ≤ 1000

• Los elementos de la matriz triangular son números naturales estrictamente positivos.

• El valor máximo de la ruta no excede ~1,000,000,000~

Ejemplo de Entrada #1

1
5 2 4
5
2 4
7 5 6
6 6 5 5
3 4 3 4 4

Ejemplo de Salida #1

6

Explicación: ~v = 1~ El número máximo de rutas es ~6~. (ver ejemplo arriba).

Ejemplo de Entrada #2

2
5 2 4
5
2 4
7 5 6
6 6 5 5
3 4 3 4 4

Ejemplo de Salida #2

1 1 1 2 2
1 2 2 2 2
1 2 3 3 4

Explicación: ~v = 2~

~st = 2~

~dr = 4~

Se imprimieron los números de la serie ~2~, ~3~ y ~4~. (ver ejemplo arriba).

Otra información útil

• una variable ~int~ ~(C++)~ o ~integer~ en ~(Pascal)~ ocupa ~4~ bytes ~(32 bits)~

• ocupa una matriz con 1000 líneas y 1000 columnas con elementos integrales ~(1000 * 1000 * 4) / (1024 * 1024) = 3.81 MB~

• Las pruebas de entrada tienen la siguiente configuración:

  #     v   n   st  dr
  0     1   20  4   10
  1     1   900 50  100
  2     1   1300    2000    3000
  3     1   1700    20000   21000
  4     2   20  6   9
  5     2   30  20 000 000  20 001 000
  6     2   60  40 030 000  40 031 000
  7     2   100 139 876 543 139 876 999
  8     2   500 137 987 000 137 988 000
  9     2   700 123 456 789 123 457 777
  10    2   900 100 000 000 100 001 000
  11    2   1000    1 999 999 999   2 000 000 000
  12    2   1010    1 000 000   1 000 001
  13    2   1020    10 123  11 111
  14    2   1100    1 999 999 999   2 000 000 000
  15    2   1200    1 000 000   1 000 001
  16    2   1300    10 123  11 111
  17    2   1500    1 999 999 999   2 000 000 000
  18    2   1600    1 000 000   1 000 999
  19    2   1700    10 123  11 123