我们正在观察 $N$ 辆卡车在道路上的运动。道路可以用一条数轴表示。数轴上的整数点表示城市，城市用其在数轴上对应的坐标表示。

所有卡车都以相同的速度行驶，且在任何时刻都没有卡车停下。每辆卡车通过相邻两个城市之间的距离需要 $1$ 分钟。

给你每辆卡车的路线。所有卡车都在同一个初始时刻开始行驶。

路线由一个包含 $k$ 个城市的数组 $A_1, A_2, \dots, A_k$ 给出。卡车从城市 $A_1$ 出发，行驶到城市 $A_2$，然后掉头行驶到城市 $A_3$，依此类推。由于卡车会掉头，因此满足：

$$A_1 < A_2 > A_3 < A_4 > \dots \text{ 或 } A_1 > A_2 < A_3 > A_4 < \dots$$

卡车掉头所需的时间可以忽略不计。

一个可能的路线是 $2, 5, 1, 7$。卡车最初在 $2$ 号城市，出发 $3$ 分钟后到达 $5$ 号城市。然后它掉头向 $1$ 号城市行驶，并在出发后 $7$ 分钟到达。接着它再次掉头向 $7$ 号城市行驶，并在时刻 $13$ 到达。

在卡车完成其路线后，外星人会出现并用他们的宇宙飞船将其带走（即卡车消失）。

对于某些卡车对，我们想知道它们在路上相遇的次数。换句话说，它们有多少次出现在相同的位置（相遇的位置不一定是整数，例如它们可以在位置 $2.5$ 相遇）。

编写一个程序，对于给定的卡车数量 $N$、它们的路线以及 $M$ 对卡车，确定每对卡车的相遇次数。

请注意：对于我们想要知道相遇次数的每对卡车，均满足以下条件：

• 在其中一辆（或两辆）卡车被外星人带走的时刻，它们不会在同一个地方。
• 在初始时刻，或者在其中一辆（或两辆）卡车掉头的时刻，它们不会在同一个地方。

上述声明并不对所有卡车对都成立，而仅对我们想要查询相遇次数的卡车对成立。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 10^5$，$1 \le M \le 10^5$），分别表示卡车的数量和我们想要查询相遇次数的卡车对数。

接下来的 $N$ 行中，第 $i$ 行包含第 $i$ 辆卡车路线的描述。

该行的第一个整数 $K_i$（$2 \le K_i \le 3 \cdot 10^5$）表示该卡车路线上的城市数量。随后是 $K_i$ 个整数 $A_j$（$1 \le A_j \le 10^9$），表示该卡车按访问顺序经过的城市的编号。

所有卡车的路线长度之和（即所有 $K_i$ 的和）不超过 $3 \cdot 10^5$。

接下来的 $M$ 行，每行包含两个整数 $(a_i, b_i)$，表示我们想要查询相遇次数的两辆卡车的编号（从 $1$ 到 $N$ 编号）。

输出格式

输出 $M$ 行。第 $i$ 行应包含输入中第 $i$ 对卡车的相遇次数。

子任务

在占总分 $50\%$ 的测试数据中，满足 $N \le 10^2$，$K_i \le 10^3$，$M \le 10^3$。

样例

输入样例 1

3 3
3 1 3 1
2 2 1
3 3 1 3
1 2
2 3
3 1

输出样例 1

1
0
2

输入样例 2

2 1
4 1 6 3 6
7 3 4 2 6 5 6 1
1 2

输出样例 2

3

输入样例 3

3 4
3 1 4 2
4 3 4 2 4
3 4 1 3
1 2
2 3
3 1
1 3

输出样例 3

2
1
2
2