Plane Add

問題文

109×10910^9 × 10^9 のマス目があり, 初め全てのマスには 00 が書かれています.

このマス目の左上のマスを (1,1)(1, 1) として上から ii 行, 左から jj 列目にあるマスを (i,j)(i, j) と表すことにします.

まず, このマス目に対して以下のクエリを NN 回行います.

  • lx,ly,rx,ry,a,b,clx, ly, rx, ry, a, b, c が入力で与えられる.
  • lxxrxlx \leq x \leq rx かつ lyyryly \leq y \leq ry である全てのマス (x,y)(x, y) に書かれた数字に a×x+b×y+ca × x + b × y + c を足す.

次に, 以下のクエリを QQ 回行ってください.

  • マス (x,y)(x, y) に書かれた数字を 998244353998244353 で割ったあまりを出力する.

制約

  • 1N,Q1051 \leq N, Q \leq 10^5
  • 1lxrx1091 \leq lx \leq rx \leq 10^9
  • 1lyry1091 \leq ly \leq ry \leq 10^9
  • 0a,b,c1090 \leq a, b, c \leq 10^9

入力

入力はすべて整数である。

N Q
lx_1 ly_1rx_1 ry_1 a_1 b_1 c_1
.
.
.
lx_N ly_N rx_N ry_N a_N b_N c_N
x_1 y_1
.
.
.
x_Q y_Q

出力

2つ目のクエリに対する答えを1行ずつ, Q行で出力してください.

サンプル

入力1
5 9
4 3 10 10 4 6 10
6 3 7 9 8 8 0
4 9 6 10 4 5 7
7 2 8 9 2 10 4
2 3 3 3 0 0 1
1 8
4 8
3 7
1 5
6 2
10 7
6 1
2 9
2 2
出力1
0
74
0
0
0
92
0
0
0
入力2
5 6
7 2 9 7 2 10 5
1 1 10 10 4 0 0
2 4 8 5 3 2 2
4 2 6 7 10 4 2
6 1 8 10 10 3 1
4 4
3 9
3 10
6 3
8 4
5 10
出力2
96
12
12
168
220
20

提出


Go (1.21)