20288번 - Metralhadora 다국어

Fulanito foi jogar um arcade das antigas. No jogo, ele pode colocar uma metralhadora em qualquer lugar da sua base, que consiste de todos os pontos (x, y) com coordenadas inteiras e x < 0. Há N inimigos no campo de batalha. O i-ésimo inimigo (1 ≤ i ≤ N) está na posição (x_i, y_i) com x_i > 0. Todas as posições são dadas de antemão.

Uma metralhadora posicionada em (x_m, y_m) cobre um ângulo de visão para a direita centrado na reta y = y_m, cujos limites são dados pelas retas y = y_m ± (x−x_m)/2 . Quando colocada, ela atinge todos os inimigos na região delimitada por esse ângulo, incluindo os localizados nas retas-limite.

Figura 1: Representação pictória da entrada de exemplo

O sistema de pontuação usado por esse jogo é desnecessariamente complicado; muitos acreditam que tal sistema foi um grande erro dos desenvolvedores (que, em resposta, afirmam com convicção que “não é um bug, é um recurso!”). Especificamente, a pontuação obtida por um dado posicionamento da metralhadora é calculada executando os seguintes passos:

• Liste os índices (i entre 1 e N) de todos os inimigos que a metralhadora atinge.
• Ordene os índices em ordem crescente, e chame os valores ordenados de i₀ < i₁ < · · · < i_k−1.
• Compute a pontuação usando a fórmula (Σi_j · 5782344^j (0 ≤ j ≤ k - 1))  mod (10⁹ + 7), onde a mod b denota o resto da divisão de a por b.
• Nota: Uma metralhadora que não atinge inimigos recebe uma pontuação exatamente igual a 0.

Para melhorar nesse jogo, Fulanito te faz Q perguntas: cada consulta pede o placar que seria obtido se posicionássemos a metralhadora numa certa posição (x_m, y_m). Para tornar o problema mais desafiador, os valores de (x_m, y_m) não são dados diretamente. Ao invés disso, são dados valores a e b que podem ser usados para calcular x_m e y_m através das fórmulas x_m = −1− (p + a) mod (10⁹ + 7)
e y_m = (p + b) mod (10⁹ + 7), onde p é a resposta da consulta anterior (p = 0 ao processar a primeira consulta).

NOTA: E garantido que a soma do número de inimigos atingidos em todas as consultas é no ´ máximo 10⁶.

A entrada consiste de várias linhas. A primeira linha da entrada contém dois inteiros N, Q (1 ≤ N, Q ≤ 10⁵), o número de inimigos e o número de consultas.

As próximas N linhas da entrada contém dois inteiros cada: x_i e y_i (1 ≤ x_i, y_i ≤ 10⁹), as coordenadas da posição do i-ésimo inimigo.

As próximas Q linhas contém dois inteiros cada: Os valores a e b (0 ≤ a, b < 10⁹+7) que especificam cada consulta, como explicado no enunciado

Para cada consulta, imprima um único inteiro contendo a resposta para a consulta.