ყულაბები

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


ბუბას აქვს n ცალი ყულაბა, რომელებიც გადანომრილია 1-დან n-მდე. იგი ყოველდღე ირჩევს ორ  L  და R ინდექსს და ამატებს თითო მონეტას ყველა ყულაბაში L-დან  R-მდე (ორივეს ჩათვლით). ბუბა ასრულებს ასეთ ოპერაციას m დღის განმავლობაში და ამის შემდეგ უჩნდება შეკითხვა: რამდენ ყულაბა შეიცავს, როგორც მინიმუმ X მონეტას. მას აქვს q შეკითხვა.

შესატანი მონაცემები: პირველი სტრიქონი შეიცავს ყულაბების რაოდენობას n (1 n 106).  მეორე სტრიქონი შეიცავს დღეების რაოდენობას m (1 m 106). მომდევნო m სტრიქონიდან თითოეული შეიცავს 2 მთელ რიცხვს L და R (1 n). შემდეგ მოდის შეკითხვების რაოდენობა q (1 q 106).  მომდევნო q სტრიქონიდან თითოეული შეიცავს ერთ მთელ რიცხვს x (1 x n).

გამოსატანი მონაცემები: ყოველი შეკითხვისათვის პასუხი გამოიტანეთ ცალკე სტრიქონზე.




მაგალითები

შესატანი მონაცემები
7 4 1 3 2 5 1 2 5 6 4 1 7 4 2 დაკოპირება
გამოსატანი მონაცემები
6 0 0 4 დაკოპირება