Fie o matrice de $N$ linii si $M$ coloane. Avem la dispozitie $P$ soareci de laborator, fiecare dintre acestia fiind dispusi sa parcurga matricea o data sau de mai multe ori dupa urmatoarele reguli:

1) Un drum incepe in casuta $(1, 1)$ si se termina in causta $(N , M)$.
2) Daca la un moment dat soarecele se afla in casuta $(X , Y)$, atunci el se poate deplasa in casuta $(X + 1, Y)$, sau in casuta $(X, Y + 1)$. Evident, daca una dintre aceste casute este pozitionata inafara matricei, soarecele nu se poate deplasa in casuta respectiva.

1) Un drum incepe in casuta $(1, 1)$ si se termina in causta $(N, M)$.
2) Daca la un moment dat soarecele se afla in casuta $(X, Y)$, atunci el se poate deplasa in casuta $(X + 1, Y)$ sau in casuta $(X, Y + 1)$. Evident, daca una dintre aceste casute este pozitionata inafara matricei, soarecele nu se poate deplasa in casuta respectiva.

Dorim sa folosim soarecii pentru a parcurge fiecare drum posibil *exact* o data. Mai mult, dorim ca fiecare din cei $P$ soareci sa parcurga acelasi numar de drumuri. In caz contrar, unii soareci se vor simti nedreptatiti si vor depune plangere la sindicatul soarecilor de laborator.

h2. Restricţii

* $1 ≤ N, M ≤ 1000000$

* $1 ≤ N, M ≤ 10^9^$

* $1 ≤ P ≤ 2000000000$ (Nu vreti sa stiti de cata branza avem nevoie..)

* Pentru teste in valoare de $60$ de puncte: $1 ≤ N, M ≤ 400$.

* Pentru teste in valoare de $40$ de puncte: $1 ≤ N, M ≤ 400$.
* Pentru teste in valoare de $60$ de puncte: $1 ≤ N, M ≤ 10^6^$.

* *Atentie!* Observati ca numele problemei si numele fisierelor de intrare/iesire nu coincid.
h2. Exemplu