問題文

\(N\) 頂点の完全グラフがあり、頂点 \(i\) には2つの数 \(a_i\) と \(b_i\) が書かれています。

そして、頂点 \(i\) と頂点 \(j\) の間の辺の長さは \(|a_i-a_j|+|b_i-b_j|\) です。

\(Q\) 個のクエリが与えられます。各クエリは \((s_i, t_i)\) という形をしています。

頂点 \(s_i\) から頂点 \(t_i\) までの最短距離を求めてください。

入力

\(N\)

\(a_1\) \(b_1\)

\(a_2\) \(b_2\)

:

\(a_N\) \(b_N\)

\(Q\)

\(s_1\) \(t_1\)

\(s_2\) \(t_2\)

:

\(s_Q\) \(t_Q\)

出力

\(Q\) 行出力しなさい。 \(i\) 行目には \(i\) 個目のクエリに対する答えを出力しなさい。

制約

• \(1≦N,Q≦10^5\)


• \(-10^9≦a_i, b_i≦10^9\)


• \(1≦s_i, t_i≦N\)


• \(s_i≠t_i\)

小課題

小課題 ≦100

• \(1≦N≦100\)

小課題 Euglena

• 追加の制約はない。