წინწიბური ზიგზაგებით დარბის

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

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

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

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


იმერიკელი მეცნიერები ისევ დავობენ წინწიბურის შესახებ. ნაწილი მას გამოგონილ არსებად თვლის, ნაწილი კი ამტკიცებს, რომ წინწიბური არსებობს, უბრალოდ ის ისე სწრაფად დარბის, რომ ვერავინ ხედავს. ერთი მეცნიერი იმასაც კი ამბობს, რომ მან შეძლო წინწიბურის მიერ გარბენილი მანძილის გაზომვა წამების მიხედვით და აღმოჩნდა, რომ ის ძალიან არათანაბრად დარბის. მეცნიერებს ახლა აინტერესებთ, რა მანძილს გაირბენს წინწიბური დროის ორ მომენტს შორის.

შესატანი მონაცემები: პირველ სტრიქონში ორი მთელი რიცხვი n და m (1<n<=1000000, 1<n< 200000) - დროის სრული ინტერვალი და შეკითხვების რაოდენობა. მეორე სტრიქონში n ცალი მთელი რიცხვი დიაპაზონში 1..100. ეს რიცხვები აღნიშნავენ იმ მანძილებს, რომელიც გაირბინა წინწიბურმა შესაბამის წამში. მომდევნო m სტრიქონიდან თითოეულში თითო შეკითხვა. შეკითხვები აღწერილია ორ-ორი რიცხვით - დროის იმ მომენტებით, რომელთა შორის გარბენილი მანძილიც გვაინტერესებს. პასუხი უნდა მოიცავდეს საწყის და საბოლოო წამებსაც.

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




მაგალითები

შესატანი მონაცემები
10 5 9 15 2 9 20 1 11 9 10 15 1 6 1 7 8 9 8 10 3 5 დაკოპირება
გამოსატანი მონაცემები
56 67 19 34 31 დაკოპირება