Empresa Maluca

Uma empresa é composta por $N$ departamentos, numerados de 1 a $N$, e divide suas atividades em projetos. Por questões logísticas a empresa decidiu que os departamentos que colaboram em um mesmo projeto devem ser vizinhos: em termos precisos, os números identificadores dos departamentos que trabalham num mesmo projeto formam um intervalo $[L, R]$ de números naturais.

Cada departamento $i$ possui $F_i$ funcionários. Os funcionários de um departamento alocado em um projeto deve formar equipes de trabalho, segundo os seguintes critérios:

• uma equipe deve conter apenas funcionários de um mesmo departamento;
• todos os funcionários do departamento devem estar alocados nas equipes;
• um funcionário não pode participar de mais de uma equipe;
• um departamento pode ter mais de uma equipe em um projeto;
• todas as equipes que trabalham um mesmo projeto devem ter o mesmo número de funcionários, independentemente de seu departamento de origem;
• o tamanho das equipes deve ser maximizado.

A empresa deseja estudar a relação entre o número de equipes que trabalhou em um projeto e o êxito daquele projeto, porém ela só possui os registros do número de funcionários de cada departamento e dos departamentos que foram alocados em cada um dos projetos. Você pode ajudá-la a determinar o número de funcionários em cada uma equipes que trabalhou em cada projeto? Considere que um novo projeto só tem início após o término do projeto anterior.

Entrada

A primeira linha da entrada contém os inteiros $N$ e $M$ $(1 \leq N, M \leq 2\times 10^5$), separados por um espaço em branco, representando o número de departamentos e o número de projetos, respectivamente.

A linha seguinte contém $N$ números $F_i$ $(1\leq F_i\leq 10^9)$, representando o número de funcionários do departamento $i$ $(1\leq i\leq N)$.

As $M$ linhas seguintes contém os registros de cada projeto, formados por um par de valores $L, R$ $(1 \leq L \leq R \leq N)$, separados por um espaço em branco, indicando que os departamentos cujos identificadores estão no intervalo $[L, R]$ trabalharam no $j$-ésimo projeto $(1\leq j\leq M)$.

Saída

Imprima $M$ linhas: a $j$-ésima linha deve conter o número de funcionários em cada equipe que trabalhou no projeto $j$, com $j = 1, 2, \ldots, M$

Exemplo de entrada 1

3 3
2 4 7
1 2
2 3
1 3

Exemplo de saída 1

2
1
1

Explicação do exemplo 1: No primeiro projeto, o departamento 1 alocou 2 equipes de 2 funcionários e o departamento 2 uma equipe de 2 funcionários; no segundo projeto, foram 4 equipes do departamento 2 e 7 do departamento 3, todas formadas por um único funcionário. Situação semelhante ocorreu no terceiro projeto, que teve 2 equipes do departamento 1, 4 do departamento 2 e 7 do departamento 3, também compostas por um único funcionário.

Exemplo de entrada 2

5 6
3 6 12 4 18
1 2
2 4
4 5
1 5
2 3
3 4

Exemplo de saída 2

3
2
2
1
6
4