题目描述

有一个二维平面，你当前位于原点，即 $(0,0)$。

你可以在平面上移动，共有 $n$ 种不同的移动方式，每种方式用一个三元组 $(x_i,y_i,c_i)$ 描述。

如果你当前位于 $(X,Y)$，那么可以选择一种移动方式 $i$，移动到 $(X+x_i,Y+y_i)$，第 $i$ 种移动方式最多使用 $c_i$ 次。

有 $Q$ 次询问，每次给定一个矩形左下角为 $(l_x,l_y)$，右上角为 $(r_x,r_y)$ 的矩形，你要通过若干次移动移动到该矩形内，输出不同方案数对 $22309287$ 取模的结果。

两种方案不同当且仅当总移动次数不同，或者某次移动选择的移动方式不同。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行三个整数 $x_i,y_i,c_i$。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，每行四个整数 $l_x,r_x,l_y,r_y$。

输出格式

一共 $Q$ 行，每行一个非负整数代表答案。

4
2 1 1
4 3 2
2 2 4
4 2 4
5
5 6 2 7
2 4 0 5
1 4 0 8
2 6 1 4
5 5 0 4

12
7
7
13
0

提示

对于 $20\%$ 的数据，$c_i\leq 20$。

对于另外 $20\%$ 的数据，$y_i=0$。

对于另外 $20\%$ 的数据，$r_x,r_y\leq 1000$。

对于另外 $20\%$ 的数据，$n\leq 2$。

对于 $100\%$ 的数据，$n\leq 4,0\leq x_i,y_i\leq 4,0\leq l_x,r_x,l_y,r_y,c_i\leq 10^{18},0\leq Q\leq 5$。

三元组 $(x_i,y_i,c_i)$ 在范围内随机生成。