#2986. 宿舍楼

宿舍楼

题目描述

某 中学的宿舍楼有 NN 层(由 11NN 表示),每层楼可以均分为 MM 个宿舍(由 11MM 表示)。

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

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

  • 左右行走,从第 xxyy 号宿舍门前走到 xxy1y-1 号或 y+1y+1 号宿舍门前,花费 11 秒;
  • 上下行走,如果有连接第 xxyy 号和第 x+1x+1yy 号的楼梯,他就可以从第 xxyy 号上到 x+1x+1 层(或正好相反),需要花费 22 秒。

C 教练有 QQ 名学生,第 ii 名学生住在第 aia_ibib_i 号宿舍。有一天,C 教练来到第 1111 号宿舍门前,要求所有学生来此集中。听到广播后,所有学生同时走出宿舍门,并按照耗时最少的路线行进。学生走出宿舍门的时间不计。

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

输入格式

11 行有 33 个正整数 N,M,QN,M,Q,表示宿舍楼有 NNMM 号,C 教练有 QQ 个学生。

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

接下来有 QQ 行,第 ii 行有 22 个正整数 ai,bia_i,b_i 表示 C 教练的第 ii 个学生住在第 aia_ibib_i 号宿舍。

输出格式

输出 QQ 行,每行 11 个非负整数。第 ii 行的表示第 ii 个学生从宿舍走到 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

样例解释

宿舍结构如下图所示,从下往上为 11NN 层,从左往右为 11MM 号。

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

下文“从第 xxyy 号下楼”表示从第 xxyy 号走到第 x1x-1yy 号,当然,要花费 22 秒。

可以发现,第 11 个学生只需走出宿舍即可到达 C 教练所在地,花费 00 秒;

22 个学生可以从第 2233 号下楼,花费 22 秒,然后往左走,花费 22 秒,总共花费 44 秒。

33 个学生可以往右走到第 3355 号下楼,然后往左走到第 2233 号下楼,然后往左走,总共花费 99 秒。

44 个学生从第 4433 号下楼,然后既可以从第 3311 号下楼,也可以从第 3355 号下楼,总共花费 1212 秒。

55 个学生从第 4444 号下楼,然后路径同第 33 号学生一致,总共花费 1818 秒。

数据范围

对于前 20%20\% 数据,N,M,Q100N,M,Q\le100

对于所有的数据,2N2×1052\le N\le2\times10^53M2×1053\le M\le 2\times10^51Q2×1051\le Q\le2\times10^51xi,1,xi,2,xi,3M1\le x_{i,1},x_{i,2},x_{i,3}\le M1aiN1\le a_i\le N1biM1\le b_i\le M