E. Elena and Travel Pass
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Elena the Ashen Witch has decided to spend some time in a magical country and is now searching for a place to stay. The country consists of $$$N$$$ cities, numbered from $$$1$$$ to $$$N$$$, connected by $$$M$$$ one-way streets. Since flying magic has been banned for intercity travel, Elena must rely on these streets to move from one city to another.

Each street is described by four integers $$$u$$$, $$$v$$$, $$$p$$$, and $$$h$$$ — meaning there is a road leading from city $$$u$$$ to city $$$v$$$ that requires a pass level of $$$p$$$ and takes $$$h$$$ hours to traverse. To use a street, Elena needs a travel pass. If she holds a pass of level $$$p$$$, she can use any streets that require a pass level less than or equal to $$$p$$$. There may be multiple streets from city $$$u$$$ to city $$$v$$$.

Elena has prepared $$$Q$$$ questions for her journey, each falling into one of the following two types:

  • Type 1: Elena is considering staying in city $$$u$$$ and wants to know the minimum pass level required so that, with that pass, the travel time from city $$$u$$$ to any city does not exceed $$$h$$$ hours.

  • Type 2: Elena is choosing where to stay and wants to find a city such that, from that city, she can reach any city within $$$h$$$ hours while requiring the lowest possible pass level. If multiple cities achieve the same minimum requirement, she will choose the one with the smallest city number, since the average cost of living there is lower.
Input

The first line contains three integers $$$N$$$, $$$M$$$, and $$$Q$$$ ($$$2 \le N \le 100$$$, $$$1 \le M \le 10^4$$$, $$$1 \le Q \le 10^5$$$) — the number of cities, the number of streets, and the number of queries, respectively.

Each of the following $$$M$$$ lines contains four integers $$$u$$$, $$$v$$$, $$$p$$$, and $$$h$$$ ($$$1 \le u, v \le N$$$, $$$u \ne v$$$, $$$1 \le p \le 10^9$$$, $$$1 \le h \le 10^9$$$), indicating that there is a road from city $$$u$$$ to city $$$v$$$ that requires a pass level of $$$p$$$ and takes $$$h$$$ hours to travel.

The next $$$Q$$$ lines describe the queries, each following one of the two formats below:

  • Type 1: 1 u h ($$$1 \le u \le N$$$, $$$1 \le h \le 10^{12}$$$, $$$u$$$ and $$$h$$$ are integers)
  • Type 2: 2 h ($$$1 \le h \le 10^{12}$$$, $$$h$$$ is integer)
Output

Output For each query $$$i$$$ ($$$1 \le i \le Q$$$), output the answer to the $$$i$$$-th query.

If the query is of Type 1, print a single integer — the minimum pass level required. If there is no valid answer, print -1.

If the query is of Type 2, print two integers — the city and the minimum pass level required. If it is impossible, print -1 -1. If there is more than one city achieving the minimum pass level, print the one with the lowest number.

Example
Input
5 6 4
1 2 1 3
2 3 1 1
3 4 1 2
4 5 1 3
5 1 1 2
1 3 2 1
1 1 9
2 8
1 1 8
1 1 5
Output
1
2 1
2
-1
Note

In the first question, Elena decides to stay in city 1. With the pass level $$$1$$$, city $$$5$$$ takes the most time out of other cities with $$$9$$$ hours — still in time.

In the second question, with a pass level $$$1$$$, Elena can travel from city $$$2$$$ to any city in $$$8$$$ hours. City $$$5$$$ also achieves the same time, but the number is higher.

In the third question, with a pass level $$$2$$$, Elena can travel from city $$$1$$$ to city $$$2$$$ in $$$3$$$ hours, to city $$$3$$$ in $$$1$$$ hour, city $$$4$$$ in $$$3$$$ hours, and city $$$5$$$ in $$$6$$$ hours.

In the fourth question, Elena cannot travel from city $$$1$$$ to city $$$5$$$ in less than $$$6$$$ hours with any pass level.