Description

具体而言，圣剑瑟尼欧里斯由 $n$ 个护符组成，每个护符有一个权值 $a_i$。威廉会进行 $k$ 次调整，每次调整一个护符，并获得与护符权值相等的疲惫值。

然而由于护符间的某种奇怪联系，威廉调整护符时有一些限制，这些限制形如 $(i,j,x,y)$，表示威廉必须在第 $i$ 次调整时调整前 $x$ 个护符中的一个 或 在第 $j$ 次调整时调整后 $y$ 个护符中的一个，否则圣剑就会崩溃。

现在，珂朵莉想知道威廉在调整完所有护符后的最小疲惫值是多少。

注意每个护符可以调整不止一遍。

Input Format

第一行三个正整数 $n,k,q$。

接下来一行 $n$ 个正整数 $a_1,a_2,a_3...a_n$。

接下来 $q$ 行，每行 $4$ 个正整数 $i,j,x,y$。

Output Format

一个数表示威廉疲惫值的最小值。

3 2 1
2 1 3
1 2 2 2 

2

3 2 1
2 1 3
1 2 1 1 

3

10 4 2
5 2 1 3 3 1 4 5 5 3 
4 3 1 7
2 4 5 5

4

Hint

样例解释：

对于第一组样例，第一次选取 $a_2$ ，第二次选取 $a_2$ 。可以证明这是满足限制的最小值。

对于第二组样例，第一次选择 $a_1$ ，第二次选择 $a_2$ 是为满足限制的最小值。

对于 $24\%$ 的数据：$1\le n \le 20,1\le k,q \le 14$ ；

对于 $56\%$ 的数据：$1\le n \le 100,1\le k,q \le 60$ ；

对于 $80\%$ 的数据：$1\le n \le 10^5, 1\le k,q\le 10^3$ ；

对于 $100\%$ 的数据：$1\le n \le 10^5,1\le k,q\le 10^4,1\le a_i\le 10^5$。

对于每一次询问有 $1 \le i,j \le k$ , $1 \le x,y \le n$。