Mars Kingdom#254
Mars Kingdom
There is a small kingdom on Mars. The kingdom contains several cities, some of which are regional centers. The kingdom also has a capital, which may or may not be a regional center. The cities are connected by one-way roads. Some roads are red, while others are blue. From every city, there is at most one outgoing road of each color.
By tradition, each year the King goes on a trip. The trip starts in the capital and consists of roads. The trip must end in a regional center. For aesthetic and historical purposes, the sequence of colors of the roads visited is recorded in the chronicles. A red road is denoted by the character '0', and a blue road is denoted by '1', resulting in a sequence of binary digits.
The young Martian Vasja is studying history. He recently found fragments of the chronicles describing the reign of King Ares. Vasja discovered the following requirements for the King's trips:
Each year, the King must choose a new route whose sequence is greater than that of the previous year. The sequences are interpreted as binary numbers with leading zeros allowed. In the first year, the King may choose any route.
If the King cannot find a new valid route, his reign ends.
Ares was very smart, always choosing routes so as to maximize the length of his reign (the number of years he could keep picking new routes).
However, as Vasja only has parts of the chronicles, some details remain unclear. For example:
What route did the King take in the -th year of his reign (years are numbered from )?
In which year did Ares take the route denoted by sequence ?
Which route did Ares take after the route denoted by ?
Which route was chosen before the route denoted by ?
Vasja is not as clever as Ares, so he asks for your help in answering these questions. Write a program that can answer them.
The first line contains five integers , , , , — the number of cities, roads, regional centers, the length of the King's route, and the number of Vasja's questions (1 \leq N \leq 50, 1 \leq M \leq 100, 1 \leq F \leq N, 1 \leq L \leq 60, 1 \leq Q \leq 10\ 000).
The cities are numbered from to . The capital is city number .
The next lines describe the road system. The -th of these lines contains three integers A_i, B_i, and C_i — meaning there is a one-way road from city A_i to city B_i of color C_i ( if the road is red, if the road is blue).
The following line contains distinct integers — the numbers of the cities that are regional centers.
The next lines each contain one question in one of the following formats:
: Which route did the King choose in the -th year of his reign (1 \leq K \leq 5 \times 10^{18})?
: In which year did the King choose the route denoted by sequence ?
: Which route did Ares choose after the route denoted by ?
: Which route was chosen before the route denoted by ?
A route is given as a sequence of characters '0' or '1'.
It is guaranteed that all queries are valid and that the answer always exists.
For each query, print one line:
For queries of the form , print a single positive integer (the year).
For all other queries, print a sequence of characters '0' or '1': the binary route corresponding to the answer.
Example 1