题目背景

小 $Y$ 不喜欢 $kdt$ 。

题目描述

跳蚤国可以看成一个无限大的二维平面，每个城市可以用一组坐标 $(x,y)$ 描述，其中 $(0,0)$ 是跳蚤国的首都。

由于新年将至，所有满足 $x\in [l_x,r_x],y\in [l_y,r_y]$ 的城市都会举行庆典，小 $Y$ 作为一个知名旅行家自然不会错过。

他现在位于首都，他准备进行一场旅行并且最终到达一个可以看到庆典的城市。为此他准备了 $n$ 个弹跳装置，第 $i$ 个具有位移偏量 $(x_i,y_i)$。假设小 $Y$ 现在位于城市 $(X,Y)$，他可以使用第 $i$ 个弹跳装置到达 $(X+x_i,Y+y_i)$ 。

弹跳装置不能无限使用，第 $i$ 个只能使用最多 $c_i$ 次。

小 $Y$ 想知道有多少种方法可以让他最终到达一个正在举行庆典的城市，两种方法不同当且仅当某一次弹跳时选择的弹跳装置的编号不同，输出答案对 $22309287$ 取模的结果。

同时你需要回答多组 $l_x,r_x,l_y,r_y$ 的询问。

输入格式

第一行两个整数 $n,Q$ 代表弹跳装置的数量以及询问的次数。

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

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

输出格式

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

样例输入

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

样例输出

5
51
16
0
30

数据规模

• $20\%$， $c_i\leq 20$
• $20\%$，$y_i=0$
• $20\%$，$r_x,r_y\leq 1000$
• $20\%$，$n\leq 2$
• $20\%$ ，无特殊限制

$100\%$，$1\leq n\leq 4,0\leq x_i,y_i\leq 4,0\leq c_i,l_x,r_x,l_y,l_y,r_y\leq 10^{18},1\leq Q\leq 5$