AMR11F  Magical Bridges
Hogwarts School of Witchcraft and Wizardry has a circular lane having N towers numbered 1 to N. Towers i and i+1 are adjacent to each other for 1 ≤ i < N and also towers 1 and N are adjacent to each other. Each of these towers has exactly F number of floors, numbered 1,2,3,..,F1,F from bottom to top. Floors i and i+1 in a tower are adjacent to each other and it takes one second to move between them. It also takes one second to move between floor 1 of a tower and floor 1 of its adjacent tower. Apart from these, there are M bridges designed for a quick escape in case of a Death Eater attack, each of which connects two floors of different towers. Each of these bridges is given as bi fi bj fj t, meaning it takes t seconds to move along this bridge that connects the floor fi of tower bi and the floor fj of tower bj. All ways are bidirectional.
Given (qbi,qfi) and (qbj,qfj), find the minimum time in seconds it takes to reach floor qfj of tower qbj, starting from floor qfi of tower qbi. You have to answer a lot of such queries.
Input (STDIN):
The first line contains the number of test cases T. T cases follow. Each test case consists of N F M in the first line. N is the number of towers, F is the number of floors in each tower and M is the number of bridges. M lines follow, each of the form bi fi bj fj t, as mentioned in the problem statement. Next line contains Q, the number of queries and Q lines follow, each of the form qbi qfi qbj qfj.
Output (STDOUT):
For each query of the form qbi qfi qbj qfj, output one line denoting the minimum time in seconds it takes to reach the floor qfj of tower qbj, starting from the floor qfi of tower qbi.
Constraints:
1 ≤ T ≤ 3
2 ≤ N, M ≤ 100
2 ≤ F ≤ 1,000,000
1 ≤ t ≤ 1,000,000
1 ≤ Q ≤ 100,000
1 ≤ bi, bj, qbi, qbj ≤ N
1 ≤ fi, fj, qfi, qfj ≤ F
Sample Input:
1
5 4 3
1 3 2 4 3
2 3 3 3 2
3 4 5 3 1
5
1 3 2 3
1 3 3 2
1 1 3 4
3 3 4 4
4 3 4 4
Sample Output:
4
5
4
6
1
hide comments
nmnsharma007:
20200802 10:09:09
Really awesome Problem.!! Last edit: 20200802 10:43:00 

joe85123:
20190801 04:45:48
interesting problem!


bluejam:
20170616 17:32:07
AC in one go.


hodobox:
20160716 00:42:35
Sigh, over 20 RE/WA because I put ios::sync_with_stdio(false) into solve() function instead of main, and it corrupted the input (but not on my PC of course...).


Dhawal Harkawat:
20151021 13:27:49
1.5 days, 220 lines of code, AC in one go, Awesome problem. Thanks @Varun Jalan. 

Maverick:
20150818 02:07:48
Awesome Awesome Awesome Problem!! Classic Problem to learn representing a graph and running Floyd Warshall.Great! Passed in Java. 

THECOLDONE:
20150630 12:06:29
very nice probem enjoy it 

Utkarsh Agarwal:
20150525 00:55:21
its simple dijisktra ?? isnt it ? 

Umair Khan:
20140918 07:16:17
Last edit: 20140923 22:42:36 

jack(chakradarraju):
20120409 12:15:12
O(Q*M) is not enough?

Added by:  Varun Jalan 
Date:  20111215 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Anil Kishore  ICPC Asia regionals, Amritapuri 2011 