დროის ლიმიტი: 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 ≤ L ≤ R ≤ 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 დაკოპირება