408530: GYM103181 K Wonderland

After a lot of work and many solved problems, you decided to take a holiday to Wonderland. Unfortunately, right before going to the beach to have a well deserved day off, the president of this land came to you with a list of requests.

Wonderland can be seen as a connected graph, containing $$$N$$$ touristic attractions, connected with each other through $$$M$$$ bidirectional roads. Each touristic attraction has a happiness factor $$$H_i$$$ which defines the happiness of a tourist after visiting it.

The president is currently working on the best strategy to get the economy back on track after the pandemic, therefore he wants to find out the answer to $$$Q$$$ questions of the following type. Given two, not necessarily distinct, touristic attractions $$$X$$$ and $$$Y$$$, an excitement factor $$$V$$$ of a tourist and a value $$$K$$$, the president wants to find out the following: Considering the set of touristic attractions that can be visited on any path from $$$X$$$ to $$$Y$$$ with the property that you do not use the same road twice, what is the level of interest of the $$$K^{th}$$$ least interesting touristic attraction for the given tourist? The level of interest of the given tourist towards the $$$i^{th}$$$ touristic attraction is given by the value $$$V$$$ $$$XOR$$$ $$$H_i$$$ (bitwise exclusive or operator). Please note that the $$$K^{th}$$$ least interesting touristic attraction for the given tourist is the one having the $$$K^{th}$$$ least level of interest.

This is a task way too hard for the programmers of this land, so the president is asking you to answer his questions.

The first line of input will contain three integers $$$N$$$, $$$M$$$, $$$Q$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq M \leq 2*10^5$$$, $$$1 \leq Q \leq 10^5$$$), representing the number of touristic attractions, the number of roads and the number of questions.

The next line will contain $$$N$$$ values $$$H_i$$$ ($$$0 \leq H_i \leq 10^6$$$), representing the happiness factors of the touristic attractions.

The next $$$M$$$ lines will each contain two values $$$X$$$ and $$$Y$$$ ($$$1 \leq X \leq N$$$, $$$1 \leq Y \leq N$$$, $$$X \neq Y$$$), representing that there is a bidirectional road between the tourist attractions $$$X$$$ and $$$Y$$$. It is guaranteed that the obtained graph is connected and that there are no self loops or multiple edges.

The last $$$Q$$$ lines will each contain four values $$$X$$$, $$$Y$$$, $$$V$$$ and $$$K$$$ ($$$1 \leq X \leq N$$$, $$$1 \leq Y \leq N$$$, $$$0 \leq V \leq 10^6$$$, $$$1 \leq K \leq 10^6$$$), representing a question.

The output contains $$$Q$$$ lines, representing the answers to the questions in the same order that they were given in the input. If there are at least $$$K$$$ tourist attractions on the paths between $$$X$$$ and $$$Y$$$ (with the property that you do not use the same road twice - note that this means that any touristic attraction can be repeated throughout the path), then print the level of interest $$$H_i$$$ $$$XOR$$$ $$$V$$$ of the $$$K^{th}$$$ least interesting one, otherwise print $$$-1$$$.

12 15 10
2 3 1 3 2 1 2 1 3 1 2 3
1 2
1 3
2 3
2 4
1 4
4 6
2 5
5 7
7 8
5 8
8 9
2 11
11 10
11 12
10 12
9 11 0 1
9 11 0 2
9 11 0 3
9 11 0 4
9 11 0 5
9 11 0 6
9 11 0 11
9 11 0 12
6 2 1 3
6 2 2 3

1
1
1
2
2
2
3
-1
2
1