文理学院程序设计在线练习


Chainlike Toshi

Time Limit: 5 Second(s)    Memory Limit: 32 MB

Total Submission(s): 3   Accepted Submission(s): 2
Problem Description

Just like Human lives on Earth, Did you live like a Chain?
Meanwhile there are lots of 2-Dimension creatures lived in “Worlus”, a huge Circle. Kytis, which is the strongest creature in Worlus, also owns a thriving civilization. They built N giant Living Towers on Worlus, labeled from 1…N. Each Tower has M-floor living area. We can uniquely mark a living area with (x, y) representing now at Living Tower x, and y is the floor.
A Kytis want to travel between the adjacent floor in the same Tower need 1 cent. Because Worlus is a Circle, each Tower have two bridges connecting two neighbor Towers. To travel between the Towers, first you need to travel to Bridge Floor, and then Kytis can pay 1 cent to travel to the another side of the Bridge, of course, the floor level will not change. As the designer of the Navigation System, now you have K transport mission, representing a Kytis’s movement. for each mission, tell Kytis the minimum cost.

Input

The first line contains a single integer T(T≤50), the number of testcase.
For each testcase, the first line contains three integers N, M, K (N*M≤200,K≤40000).
Then One line contains N integers, the i-th integers means the Bridge floor between tower (i) and (i+1) .notice that the next Tower of Tower N is Tower 1.
Then K line follows, each line contains Four integers A, B, C, D, which means that a Kytis wants to travel from Tower A, B floor, to Tower C, floor D.( 1≤A, C≤N 1≤B, D≤M) .

Output

For each transport mission, output an integer in a line represent the minimum cost.(cent)

Sample Input
2 
2 2 2 
1 2
1 1 1 2
1 1 2 2
3 3 3
1 2 3 
1 1 2 2 
1 1 3 3 
2 3 3 3
Sample Output
1
2
2
3
3
Source

2018市赛