În gradina lui Ion sunt N flori pe care acesta le-a asezat cu grija într-un cerc. Pentru a tine minte pe care le-a udat si pe care nu, Ion le-a numerotat cu numere de la 1 la N astfel: a ales o floare pe care a numerotat-o cu 1 si plimbându-se de-a lungul cercului în sensul acelor de ceasornic, le-a numerotat pe celelalte cu numere consecutive.
Doua albinute (una lucratoare si alta inspector) sar din floare în floare, având un obicei destul de ciudat: daca una dintre ele este în floarea cu numarul x, ea va sari peste K flori (în sensul acelor de ceasornic). De exemplu, pentru N=10, K=3, daca o albinuta se afla în floarea cu numarul 6, ea va sari în floarea cu numarul 9, iar daca se afla în floarea cu numarul 10, va sari în floarea cu numarul 3.
Pentru a putea duce ce a cules la stup, albinuta lucratoare face mai multe drumuri. La drumul cu numarul i, albinuta începe din floarea cu numarul a_i si sare din floare în floare de b_i ori. De fiecare data când ajunge într-o floare la drumul i, albinuta culege c_i masuri de polen din acea floare. Albinuta culege polen si din prima floare din care pleaca si poate culege polen de mai multe ori dintr-o floare, daca la drumul respectiv va trece de mai multe ori prin acea floare.
O albinuta inspector verifica din când în când performanta albinutei lucratoare. Ea face drumuri la fel ca albinuta lucratoare (la un drum i, începe din floarea cu numarul ai si face b_i salturi), dar în loc sa culeaga polen, calculeaza câte masuri de polen a cules în total albinuta lucratoare pâna la momentul respectiv din florile de pe acest drum. Albinuta inspector ia în considerare si floarea din care pleaca, si daca la drumul respectiv trece de mai multe ori printr-o floare, va aduna la total de fiecare data numarul de masuri de polen din acea floare.

Cerinta

Scrieti un program care sa gaseasca raspunsul (modulo 30103) pentru fiecare drum al albinutei inspector.

Date de intrare

Fisierul de intrare albinuta.in contine pe prima linie numerele N, K si M (M reprezinta numarul total de drumuri, atât ale albinutei lucratoare cât si ale albinutei inspector).
Pe urmatoarele M linii se vor afla triplete de forma a_i, b_i, c_i.
Daca c_i <> 0, atunci acest triplet reprezinta un drum al albinutei lucratoare.
Daca c_i = 0, atunci acest triplet reprezinta un drum al albinutei inspector.

Date de iesire

Fisierul de iesire albinuta.out va avea atâtea linii câte drumuri ale albinutei inspector exista. Fiecare linie va contine un numar natural reprezentând raspunsul cerut (modulo 30103).

Restrictii si precizari

• 1 <= N < 50 000
• 1 <= K < 20
• 1 <= M < 50 000
• 1 <= a_i <= N
• 0 <= b_i < N
• 0 <= c_i < 100
  

Exemplu

Tiberiu Danet
Universitatea Bucuresti
Contact:tiberiu@danet.ro