Content:
简体中文
英雄是一款線上遊戲,在這款遊戲中的地圖是以 N×N 的格子方式呈現。在一般的情況下,每次玩家只能往上、下、左、右四個方向移動一格。但是,在某些格子之中備有一些傳送門(如圖中有綠色點的格子),這個傳送門讓你也可以選擇要往左上、左下、右下和右上移動一格,也就是可以前往周圍八格。
現在你的公會被攻打了,你必須要趕到你的公會去幫忙,然而你在這個地圖的左上角(如圖中有紅色點的格子),而公會卻在右下角(如圖中有藍色點的格子)。幸運的是,你有所有傳送門的座標,你希望能夠妥善的利用傳送門讓你縮短到公會的時間。每次從一格移動到另一格則時間加一,你希望能夠用最短的時間到公會的位置。
Input:
輸入的第一行有一個正整數T,代表測試資料的組數(1<=T<=100)。
每一組測試資料的第一行有一個整數 N (1<=N<=10000000)。第二行有一個數字 K (0<=K<=50000),代表總共有幾個傳送門。第三行有 K 個數字 X1,X2,…,XK (1<=Xi<=N),代表這 K 個傳送門的 x 座標。第四行有 K 個數字 Y1,Y2,…,YK (1<=Yi<=N),代表這 K 個傳送門的 y 座標。座標從左上角開始算,左上角為(1,1)。
Output:
Sample Input:
2 14 5 4 9 5 8 12 4 7 10 11 12 4 3 2 2 3 2 1 2
Sample Output :
22 4
Hint
:
Author
: