有 nnn 个未知数，分别为 x1,x2,⋯ ,xnx_1, x_2, \cdots, x_nx1,x2,⋯,xn ，这些未知数之间需要满足 mmm 个条件，每个条件是以下三种形式之一：
其中 xa,xbx_a, x_bxa,xb 代表两个不同的未知数，ccc 代表一个常数。
你需要回答 qqq 次询问，每次询问给出两个正整数 a,ba, ba,b ，你需要计算出 max(xa−xb)max(x_a - x_b)max(xa−xb) 。
第一行两个正整数 n,m,qn, m, qn,m,q ，分别表示未知数的个数和条件的个数。
接下来 mmm 行，每行四个正整数 k,a,b,ck, a, b, ck,a,b,c ，表示一个条件。k=1k = 1k=1 时，xa≤xb+cx_a \le x_b + cxa≤xb+c；k=2k = 2k=2 时，xa=xb+cx_a = x_b + cxa=xb+c；k=3k = 3k=3 时，xa≥xb+cx_a \ge x_b + cxa≥xb+c 。
接下来 qqq 行，每行两个正整数 a,ba, ba,b ，表示一次询问。
对于每次询问输出一行，总共输出 qqq 行。
每行一个整数，表示 max(xa−xb)max(x_a - x_b)max(xa−xb)。
数据保证每次询问一定有整数解。
3 3 2 1 1 2 0 1 2 3 1 3 3 1 2 1 2 1 3
0 -2
3 3 2 1 1 2 3 1 2 3 4 1 3 1 5 1 3 3 2
7 8
1≤n≤5001 \le n \le 5001≤n≤500
1≤m, q≤1041 \le m,\ q \le 10^41≤m, q≤104
1≤a, b≤n1 \le a,\ b \le n1≤a, b≤n
−105≤c≤105-10^5 \le c \le 10^5−105≤c≤105