分数: 500 点
问题陈述
AtCoder王国的道路位于xy平面上,是以下线 x=n 和 y=n 对于所有整数 n。 其中,行 x=Bn 和 y=Bn 对于所有整数 n 是主要道路。
当高桥在 (x,y),他可以移动到 (x,y-1), (x,y+1), (x+1,y),或 (x-1,y)。 每个动作都需要 1 沿着主要道路的第二个和 K 秒,否则。
求高桥需要的最小秒数 (S_x, S_y) to (G_x, G_y).
你将会有 T 测试用例解决。
约束
- 1 \le T \le 2 \times 10^5
- 1 \le B,K \le 10^9
- 0 \le S_x,S_y,G_x,G_y \le 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{testcase}_1
\mathrm{testcase}_2
\vdots
\mathrm{testcase}_T
每个测试用例均采用以下格式:
B K S_x S_y G_x G_y
输出
打印 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
4 3 4 2 2 4 4 5 6 2 3 2 3 1 1000000000 0 0 1000000000 1000000000 1000000000 1000000000 500000000 500000000 1000000000 1000000000
示例输出 1
10 0 2000000000 500000000500000000
对于 1-st 测试用例,他可以从 (2,2) to (2,3) in 4 秒,从 (2,3) to (4,3) in 2 秒,并且从 (4,3) to (4,4) in 4 秒数 (2,2) to (4,4) in 10 秒。不可能在不到 10 秒,所以答案是 10.
对于 2-nd 测试用例,他已经在 (G_x, G_y) 在开头,所以答案是 0.
示例输入 2
10 928184439 674654465 203937094 186855052 851783856 805293696 55480262 448852233 823161539 786348805 550018803 322680316 891870741 235679524 32164572 497841190 620600021 96487871 321502816 428964257 499656016 521484999 717623189 824784374 144040837 680268887 76238777 371138006 350230937 78690135 768922620 799628518 403830696 60449731 218880692 88319939 482031503 121412614 472330444 284479575 949635609 427232765 389524418 132987043 656496997 678732442 23028233 488463974 857778764 629964237 714551548 739330018 579247790 874251485 461612428 535402609 555160129 833592114 44418273 287363785
示例输出 2
177606591118701316 6205925075792263 30320747646118343 84136273267803188 83764071874751489 118960470930399064 2929499649126153 16403238161749820 84995699148879437 71771264361119335