베라와 현대 미술

위대한 화가 피카우소에게 영감을 받은 베라는 자기만의 대작을 그리기로 했다. 그림판은 무한히 넓은 2차원 좌표평면이다. 베라는 2의 거듭제곱(1, 2, 4, 8, 16, ...)을 좋아해서 2의 거듭제곱인 간격으로 같은 점찍기를 반복한다.

베라는 색칠을 $N$번 한다. $i$번째 색칠은 세 정수 $x_i$, $y_i$, $v_i$로 나타낸다. $a_i$를 $x_i$ 이하인 가장 큰 2의 거듭제곱, $b_i$를 $y_i$ 이하인 가장 큰 2의 거듭제곱이라고 하자. 베라는 $p$, $q$가 음이 아닌 정수일 때 $(x_i + a_i p,\ y_i + b_i q)$ 꼴인 모든 점에 색이 $v_i$인 물감 방울을 하나씩 떨어뜨린다. 한 점에 물감 방울이 여러 개 떨어질 수 있고, 같은 색이 여러 번 떨어질 수도 있다.

그다음 베라는 질문을 $Q$개 한다. $j$번째 질문은 점 $(r_j, c_j)$의 색을 묻는다. 한 점의 색은 그 점에 떨어진 물감 방울의 색을 모두 더한 값이다. 물감 방울이 하나도 없는 점의 색은 0이다.

베라의 미술 조수가 된 당신이 질문에 답해야 한다.

첫째 줄에 정수 $N$, $Q$가 공백 하나를 사이에 두고 주어진다. ($1 \le N, Q \le 2 \cdot 10^5$)

다음 $N$개 줄에 색이 $v_i$인 물감 방울을 나타내는 세 정수 $x_i$, $y_i$, $v_i$가 공백으로 구분되어 한 줄에 하나씩 주어진다. ($1 \le i \le N$; $1 \le v_i \le 10000$; $1 \le x_i, y_i \le 10^{18}$)

다음 $Q$개 줄에 점 $(r_j, c_j)$에 대한 질문을 나타내는 두 정수 $r_j$, $c_j$가 공백으로 구분되어 한 줄에 하나씩 주어진다. ($1 \le j \le Q$; $1 \le r_j, c_j \le 10^{18}$)

$Q$개 줄을 출력한다. $j$번째 줄에는 점 $(r_j, c_j)$의 색을 정수 하나로 출력한다.

첫 번째 예제에서 색 1, 2, 3, 4, 5를 각각 빨강, 파랑, 초록, 주황, 보라라고 하자. $p$, $q$가 음이 아닌 정수일 때 물감 방울은 다음과 같이 떨어진다.

• 점 $(1 + p,\ 2 + 2q)$에 빨간 물감 방울
• 점 $(3 + 2p,\ 4 + 4q)$에 파란 물감 방울
• 점 $(4 + 4p,\ 5 + 4q)$에 초록 물감 방울
• 점 $(6 + 4p,\ 3 + 2q)$에 주황 물감 방울
• 점 $(7 + 4p,\ 1 + q)$에 보라 물감 방울

$(0, 0)$부터 $(11, 11)$까지 그림은 다음과 같다.

점 $(7, 8)$에는 빨강, 파랑, 보라 방울이 있으므로 색이 $1 + 2 + 5 = 8$이고, 점 $(5, 9)$에는 방울이 없으므로 색이 0이다.