John has a directed acyclic graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges. Each vertex $$$u$$$, $$$1\leq u\leq n$$$, has a value $$$a_{u}$$$ associated to it.
Let's define the beauty of a simple path $$$P=u_{1}u_{2}...u_{l-1}u_{l}$$$ over the graph $$$G$$$ as: $$$$$$ a_{u_{1}}\& a_{u_{2}}\&...\& a_{u_{l-1}}\& a_{u_{l}}$$$$$$ where $$$\&$$$ denotes the bitwise and operator.
Find the maximal possible beauty of a path $$$P$$$ consisting of exactly $$$k$$$ vertices over the graph $$$G$$$.
The first line contains three integers: $$$n$$$, $$$m$$$, $$$k$$$ $$$(2\leq n\leq 2 \cdot 10^5, n-1\leq m\leq 2 \cdot 10^5, 1\leq k \leq n)$$$ — the number of vertices of the graph $$$G$$$, the number of edges of the graph and the required length of the path, respectively.
The second line contains $$$n$$$ integers $$$a_{1}, a_{2},...,a_{n-1}, a_{n}$$$ $$$(0\leq a_{i} \lt 2^{20})$$$.
Each line $$$i$$$ of the next $$$m$$$ lines contains two integers: $$$u_{i}, v_{i}$$$, meaning that there is a directed edge from vertex $$$u_{i}$$$ to vertex $$$v_{i}$$$.
The output must contain a single integer, $$$x$$$ — the maximal possible value of the beauty of a path of length exactly $$$k$$$ over the graph $$$G$$$.
5 8 4 11 26 15 3 26 1 5 2 3 2 5 3 1 3 5 4 1 4 3 4 5
10
7 12 4 36 47 47 31 33 15 34 1 6 1 7 2 4 2 5 3 2 3 7 4 1 4 5 4 6 5 7 6 5 6 7
32
