题目描述

题目背景

清晨的第一缕风，带着山间特有的清冽，拂过守矢神社古朴的注连绳，发出细微的呜咽，仿佛风也在进行着虔诚的参拜。东风谷早苗已经换上了巫女装束，正拿着雪白的抹布，一丝不苟地擦拭着社务所的每一张桌椅、每一个角落。虽然幻想乡的参拜客远不如外界多，但她依然将这里整理得纤尘不染，这是她的职责，也是她连接“现人神”与信仰的日常修行。

“神明大人看到整洁的神社，心情也会变好吧。”她这样想着，嘴角噙着温柔的笑意。

神社的殿顶之上，八坂神奈子随意地坐着，一条腿曲起，手搭在膝盖上。她锐利的目光越过鸟居，眺望着在晨雾中若隐若现的妖怪之山和更远处的博丽神社，仿佛在审视着自己的“国度”。风缠绕着她的发丝和御柱，带来远方的气息。

而在神社后方，那片由她力量开垦出的肥沃田地里，泄矢诹访子正蹲在田埂上。她戴着标志性的帽子，帽檐下的表情看不真切。只见她小心翼翼地从怀里掏出一个小布包，打开，里面是几颗光滑圆润的鹅卵石。她左看右看，选了个阳光最好的位置，然后郑重其事地、将一块画着滑稽青蛙笑脸的石头，立在了田埂边。接着是第二块、第三块……很快，一排憨态可掬的“青蛙石像”卫兵，就精神抖擞地“守卫”起这片田地。

早苗擦拭完毕，端着水盆出来倒水时，正好看到这一幕。她忍不住轻笑出声，心里暖暖的。这就是她的日常，她的神社，她的家。风再次吹过，带来了泥土的芬芳和隐约的、青蛙的呱呱声（或许是错觉？）。

题目描述

给定 \(n\) 个圆形区域，第 \(i\) 个圆的圆心为 \(\left(p_i, q_i\right)\)，半径为 \(r_i\)。圆形区域为 \(\{ \left(x, y\right)\mid \left(x-p_i\right)^2+ \left(y-q_i\right)^2 \le r_i^2\}\)。保证圆的半径不超过 \(30\)。

给定 \(m\) 次询问。每次询问给定 \(x_{i, 1}\)， \(y_{i, 1}\)， \(x_{i, 2}\)， \(y_{i, 2}\) （\(x_{i, 1} \le x_{i, 2}\)， \(y_{i, 1} \le y_{i, 2}\)），表示四个顶点分别位于 \(\left(x_{i, 1}, y_{i, 1}\right)\)， \(\left(x_{i, 1}, y_{i, 2}\right)\)， \(\left(x_{i, 2}, y_{i, 2}\right)\)， \(\left(x_{i, 2}, y_{i, 1}\right)\) 的矩形区域 \(\{(x, y)\mid x\in [x_{i, 1}, x_{i, 2}], y \in [y_{i, 1}, y_{i, 2}]\}\)。每次询问求出，在给定的 \(n\) 个圆中，与给定的矩形区域有公共点的圆的数量。

输入格式

输入的第一行包含一个整数 \(t\) （\(1 \le t \le 1000\)），表示测试用例的数量。

接下来是 \(t\) 个测试用例的描述。

每个测试用例的第一行包含两个整数 \(n\) 和 \(m\) （\(1 \le n \le 1.5 \times 10^6\)， \(1 \le m \le 10^4\)），分别表示圆的个数和询问个数。

接下来 \(n\) 行，第 \(i\) 行包含三个整数 \(p_i\)， \(q_i\) 和 \(r_i\) （\(1 \le p_i, q_i \le 10^9\)， \(1 \le r_i \le 30\)），表示第 \(i\) 个圆形区域圆心在 \(\left(p_i, q_i\right)\)，半径为 \(r_i\)。

接下来 \(m\) 行，第 \(i\) 行包含四个整数 \(x_{i, 1}\)， \(y_{i, 1}\)， \(x_{i, 2}\)， \(y_{i, 2}\) （\(1 \le x_{i, 1} \le x_{i, 2} \le 10^9\)， \(1 \le y_{i, 1} \le y_{i, 2} \le 10^9\)），表示询问的矩形区域的顶点。

保证所有测试用例中 \(n\) 的总和不超过 \(3 \times 10^6\)， \(m\) 的总和不超过 \(2 \times 10^4\)。

输出格式

对于每个测试用例，输出 \(m\) 行，每行输出一个非负整数，表示第 \(i\) 个询问的答案。

样例输入

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

样例输出

3
4
4
7

提示

在样例测试用例 1 中，查询给定的矩形，与第 \(2\) 个、第 \(3\) 个、第 \(4\) 个圆形，总计三个圆形有公共点。