Efficient Travel Planning

Kuno wants to travel from city A to city B. There are N cities numbered from 0 to N-1, where city 0 represents A and city N-1 represents B. The larger the index, the closer the city is to B. During his journey, he may stop at intermediate cities; however, the stops must meet the following conditions:

• The city of the i-th stop must be strictly closer to B than the city of the i-1-th stop. (We treat the 0-th stop as city A.)
• The total travel time, from leaving A until leaving B after his stay in B, is no more than M days. In other words, you are not allowed to stay at A but you are allowed to stay at B.

Kuno’s travel is based on available air routes and the hotel systems in the cities. In each city i there are H flight routes. Each route is represented by a pair \((j,k)\), which means that you can fly from city i to city j, but once you use this route you must stay in city j for at least \(k\) days. In particular, every city has a route that goes directly to city B.

Note that there might be multiple routes with identical information (or same start and end cities). In such cases, treat them as different routes. Also, you should ignore any route that leads away from city B (i.e. if the destination city is not closer to B than the current city, namely, if \(j \le i\)).

Time spent on the plane is negligible. When you arrive at any city, the arrival day immediately counts as a day of stay (even if you leave on the same day).

Your task is: for each d in \([1, M]\), count the number of different travel plans where the journey from leaving A to leaving B takes exactly \(d\) days. If the number of plans exceeds \(5\times10^8\), simply output \(5\times10^8+1\) for that day.

Two travel plans are considered different if any one of the following holds:

1. There is some city that is visited (i.e. a stop is included) in one plan but not in the other.
2. The departure day from some city (including city B) differs between the two plans.
3. For some flight from city i to city j, the routes used in the two plans are different (even if the departure and arrival days are the same).

Input Format:

Line 1: Three integers N, M, H
For each city i from 0 to N-2:
    Next H lines: two integers j and k, representing a flight route (from city i to city j requiring a minimum stay of k days)

Output Format:

Output M space‐separated integers. The d-th integer (for d from 1 to M) is the number of travel plans that take exactly d days. (If the number exceeds 5×10^8, output 500000001 instead for that day.)

inputFormat

The first line contains three integers \(N\), \(M\), and \(H\) separated by spaces. This is followed by \(H\) lines for each city from 0 to \(N-2\). Each of these lines contains two integers \(j\) and \(k\), indicating a flight route from the current city to city \(j\) that requires a minimum stay of \(k\) days at city \(j</em>).

Note: Routes where \(j \le i\) (i.e. not moving closer to B) should be ignored. Every city is guaranteed to have at least one route that goes directly to city B (i.e. where \(j = N-1\)).

outputFormat

Output \(M\) space‐separated integers on a single line. The \(d\)-th integer is the number of travel plans that take exactly \(d\) days from leaving A until leaving B. If the count exceeds \(5\times10^8\), output \(500000001\) for that day.

sample

2 3 1
1 1

1 1 1