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

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

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

მაგალითები

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

გამოსატანი მონაცემები
6
0
0
4
                  დაკოპირება