An NGO has N members with IDs from 1 to N. Previously in the NGO all the members would perform similar types of environment service activities during weekends. Now according to the new rule, the NGO has decided to do X new types of activities. All these activities are identified by a unique ID from 1 to X. The previous type of activity had the ID 0. For Y hours during weekends, a group of members with consecutive member IDs are selected per hour to do X new types of activities. Any member not selected for that hour is performing the previous types of assigned activities. The head of the NGO needs to find out the maximum number of members performing a certain type of activity for every Y working hours.
Write an algorithm to find the maximum number of members performing a certain type of activity for every Y working hours.
Input
The first line of the input consists of three space-separated integers numOfMembers, numOfActivities, and numOfHours, representing the number of members (N), the number of new types of activities (X) and the number of working hours (Y). respectively.
The next Y lines consist of three space-separated integers first, last and activity Type, representing the selected range of member IDs handling one of request per hour, and the ID of the activity type being handled by the employees, respectively.
Output
Print Y space-separated integers representing the maximum number of members performing a certain type of activity for every Y working hours.
Constraints
1<= numOfMembers,numOfActivites numOfHourss <=1e5
1<= firsts <= lasts <= numOfMembers
1 <= activityTypes <= numOfActivities
EXAMPLE:
INPUT
5 5 4
2 3 5
4 5 2
4 5 1
Output : 3 2 2 5