Archiwum zadań programistycznych WWSI

Mieszkańcy p państw położonych wzdłuż linii wybrzeża naszego kontynentu mają już dość noszenia ogromnej liczby monet w swoich sakiewkach, które pod ich ciężarem często się przerywają. W związku z powyższym władcy niektórych krajów sąsiadujących ze sobą postanowili wprowadzić nową walutę minimalizując jednocześnie liczbę monet będących w obiegu. Jako, że żaden z miłościwie nam panujących nie ma zamiaru przemęczać się wykonywaniem obliczeń, dlatego też to zadanie przypadło Tobie.

Mając daną grupę sąsiadujących ze sobą państw oblicz ile monet powinno otrzymać każde z nich pamiętając o tym, że łączna liczba monet nowej waluty powinna być jak najmniejsza, zaś stosunek liczby nowych monet dowolnej pary państw musi być identyczny jak w przypadku starej waluty.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite p oraz q (1 ≤ p, q ≤ 1000) oznaczające odpowiednio liczbę państw oraz liczbę zapytań do obliczenia. W drugiej linii wejścia znajduje się p liczb z przedziału od 1 do 10⁶ określających bieżącą liczbę monet w danym państwie. W kolejnych q liniach znajdują się zapytania. Każde z nich składa się z dwóch liczb a oraz b (1 ≤ a < b ≤ p) określających początek i koniec przedziału państw, dla których należy wyliczyć nową liczbę monet.

Wyjście

Dla każdego zapytania należy w osobnej linii wypisać liczbę monet jakie otrzyma każde z państw w danym przedziale, zaczynając od miasta na pozycji a a kończąc na mieście na pozycji b.

Przykład

Wejście

5 2
4 8 6 2 2
1 2
2 5

Wyjście

1 2 
4 3 1 1