albinuta

Ion's garden has N flowers which he carefully planted in a circle. In order to remember which he watered and which not, Ion numbered them from 1 to N, as follows: he picked a flower and numbered it 1 and, moving clockwise around the circle, he numbered the rest consecutively.
Two bees (a worker bee and an inspector bee) hop from flower to flower and have a pretty peculiar habit: if one of them is on flower number x, it'll jump over K flowers (clockwise). E.g. for N=10, K=3, if a bee is on flower number 6, it'll jump to flower number 9, and if it's on flower number 10, it'll jump to flower number 3.
The worker bee makes more than one trip to take back to the hive what it has gathered. On trip number i, the bee starts from flower number a_i and hops from flower to flower b_i times. Every time it reaches a flower on trip i, the bee gathers c_i units of pollen from that flower. The bee also gathers pollen from the first flower it leaves from and may gather pollen more than once from a flower, if during said trip it passes through that flower more than once.
An inspector bee checks the worker bee's performance from time to time. It makes trips the same way the worker bee does (during a trip i, it begins from flower number ai and makes b_i jumps), but instead of gathering pollen it calculates how many units of pollen the worker bee has collected until then from the flowers on this trip. The inspector bee also takes into consideration the flower it leaves from and if it passes through one flower more than once on that trip it will add number of pollen units from that flower to the total every time.

Task

Write a program that finds the answer (remainder when divided by 30103) for every trip of the inspector bee.

Input Data

Input file albinuta.in contains on line one numbers N, K and M (M represents the total number of trips, both of the worker bee and of the inspector bee).
The following M lines will contain triplets under the form a_i, b_i, c_i.
If c_i <> 0, then this triplet represents a trip of the worker bee.
If c_i = 0, then this triplet represents a trip of the inspector bee.

Output Data

Output file albinuta.out will have as many lines as there are trips of the inspector bee. Each line will contain a positive integer representing the requested answer (remainder when divided by 30103).

Constraints and Statements

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

Time limit: 1 second/test

Tiberiu Danet
University of Bucharest
Contact:tiberiu@danet.ro