기관총

Fulanito는 오래된 아케이드 게임을 하러 갔다. 이 게임에서 그는 자신의 기지 안 임의의 위치에 기관총을 설치할 수 있는데, 기지는 좌표가 정수이고 $x < 0$인 모든 점 $(x, y)$로 이루어져 있다. 전장에는 $N$명의 적이 있다. $i$번째 적($1 \le i \le N$)은 $x_i > 0$인 위치 $(x_i, y_i)$에 있다. 모든 위치는 미리 주어진다.

$(x_m, y_m)$에 설치된 기관총은 직선 $y = y_m$을 중심으로 오른쪽을 향하는 시야각을 가지며, 그 경계는 직선 $y = y_m \pm (x - x_m)/2$로 주어진다. 설치되면 이 각도로 둘러싸인 영역 안의 모든 적을 타격하며, 경계선 위에 있는 적도 포함한다.

그림 1: 예제 입력의 그림 표현

이 게임의 점수 체계는 쓸데없이 복잡하다. 많은 이들은 이 체계가 개발자들의 큰 실수였다고 생각한다(개발자들은 이에 대해 “버그가 아니라 기능이다!”라고 단호히 주장한다). 구체적으로, 기관총을 어떤 위치에 두었을 때 얻는 점수는 다음 단계로 계산한다:

• 기관총이 타격하는 모든 적의 인덱스($1 \le i \le N$)를 나열한다.
• 인덱스를 오름차순으로 정렬하고, 정렬된 값을 $i_0 < i_1 < \cdots < i_{k-1}$이라 한다.
• $(\sum_{j=0}^{k-1} i_j \cdot 5782344^j) \bmod (10^9 + 7)$ 공식으로 점수를 계산한다. 여기서 $a \bmod b$는 $a$를 $b$로 나눈 나머지를 뜻한다.
• 참고: 적을 하나도 타격하지 못한 기관총의 점수는 정확히 0이다.

이 게임을 더 잘하기 위해 Fulanito는 $Q$개의 질문을 한다. 각 질문은 기관총을 특정 위치 $(x_m, y_m)$에 두었을 때 얻을 점수를 묻는다. 문제를 더 어렵게 만들기 위해 $(x_m, y_m)$ 값은 직접 주어지지 않는다. 대신 $a$와 $b$가 주어지고, 다음 공식으로 $x_m$과 $y_m$을 계산한다: $x_m = -1 - (p + a) \bmod (10^9 + 7)$이고 $y_m = (p + b) \bmod (10^9 + 7)$. 여기서 $p$는 이전 질문의 답이며, 첫 질문을 처리할 때는 $p = 0$이다.

참고: 모든 질문에서 타격한 적의 수의 합은 최대 $10^6$임이 보장된다.

입력은 여러 줄로 이루어진다. 첫째 줄에는 적의 수와 질문의 수를 나타내는 두 정수 $N, Q$($1 \le N, Q \le 10^5$)가 주어진다.

다음 $N$개 줄에는 각각 두 정수 $x_i$와 $y_i$($1 \le x_i, y_i \le 10^9$)가 주어지며, 이는 $i$번째 적의 위치 좌표이다.

다음 $Q$개 줄에는 각각 두 정수 $a$와 $b$($0 \le a, b < 10^9 + 7$)가 주어지며, 이는 문제 설명에서 설명한 대로 각 질문을 지정한다.

각 질문마다 질문의 답을 담은 정수를 한 줄에 하나씩 출력한다.