题目描述

某 中学的宿舍楼有 $N$ 层（由 $1$ 到 $N$ 表示），每层楼可以均分为 $M$ 个宿舍（由 $1$ 到 $M$ 表示）。

同时，除顶楼外，每层楼都有恰好 $3$ 个楼梯通向上一层。如果一个楼梯下端在 $x$ 层 $y$ 号宿舍门前，它的上端就在 $x+1$ 层的 $y$ 宿舍门前。

一个人在宿舍里行走，有如下几种可能：

• 左右行走，从第 $x$ 层 $y$ 号宿舍门前走到 $x$ 层 $y-1$ 号或 $y+1$ 号宿舍门前，花费 $1$ 秒；
• 上下行走，如果有连接第 $x$ 层 $y$ 号和第 $x+1$ 层 $y$ 号的楼梯，他就可以从第 $x$ 层 $y$ 号上到 $x+1$ 层（或正好相反），需要花费 $2$ 秒。

C 教练有 $Q$ 名学生，第 $i$ 名学生住在第 $a_i$ 层 $b_i$ 号宿舍。有一天，C 教练来到第 $1$ 层 $1$ 号宿舍门前，要求所有学生来此集中。听到广播后，所有学生同时走出宿舍门，并按照耗时最少的路线行进。学生走出宿舍门的时间不计。

请问，每个学生走到 C 教练所在地分别需要多少秒？

输入格式

第 $1$ 行有 $3$ 个正整数 $N,M,Q$，表示宿舍楼有 $N$ 层 $M$ 号，C 教练有 $Q$ 个学生。

接下来有 $N-1$ 行，第 $i$ 行有 $3$ 个正整数 $x_{i,1},x_{i,2},x_{i,3}$，表示连接第 $i$ 层与第 $i+1$ 层的楼梯的位置。

接下来有 $Q$ 行，第 $i$ 行有 $2$ 个正整数 $a_i,b_i$ 表示 C 教练的第 $i$ 个学生住在第 $a_i$ 层 $b_i$ 号宿舍。

输出格式

输出 $Q$ 行，每行 $1$ 个非负整数。第 $i$ 行的表示第 $i$ 个学生从宿舍走到 C 教练所在地需要花费多少秒的时间。

4 11 5
3 6 10
1 5 8
2 3 4
1 1
2 3
3 4
4 3
4 11

0
4
9
12
18

样例解释

宿舍结构如下图所示，从下往上为 $1$ 到 $N$ 层，从左往右为 $1$ 到 $M$ 号。

其中，红线表示两地间有楼梯连接，蓝色数字表示第 $i$ 个学生住在这里。

下文“从第 $x$ 层 $y$ 号下楼”表示从第 $x$ 层 $y$ 号走到第 $x-1$ 层 $y$ 号，当然，要花费 $2$ 秒。

可以发现，第 $1$ 个学生只需走出宿舍即可到达 C 教练所在地，花费 $0$ 秒；

第 $2$ 个学生可以从第 $2$ 层 $3$ 号下楼，花费 $2$ 秒，然后往左走，花费 $2$ 秒，总共花费 $4$ 秒。

第 $3$ 个学生可以往右走到第 $3$ 层 $5$ 号下楼，然后往左走到第 $2$ 层 $3$ 号下楼，然后往左走，总共花费 $9$ 秒。

第 $4$ 个学生从第 $4$ 层 $3$ 号下楼，然后既可以从第 $3$ 层 $1$ 号下楼，也可以从第 $3$ 层 $5$ 号下楼，总共花费 $12$ 秒。

第 $5$ 个学生从第 $4$ 层 $4$ 号下楼，然后路径同第 $3$ 号学生一致，总共花费 $18$ 秒。

数据范围

对于前 $20\%$ 数据，$N,M,Q\le100$；

对于所有的数据，$2\le N\le2\times10^5$，$3\le M\le 2\times10^5$，$1\le Q\le2\times10^5$，$1\le x_{i,1},x_{i,2},x_{i,3}\le M$，$1\le a_i\le N$，$1\le b_i\le M$。