There is a small Kingdom on Mars. There are some cities in the Kingdom, some of them are regional centers. The Kingdom has also a capital which may be a regional center or not. Cities are connected with one-way roads. Some of the roads are red and the remaining ones are blue. There is no more than one road of each color getting out of each city. There is a tradition that the King goes to a trip each year. The trip starts from the capital city and consists of \textbf{L} roads. The trip must end in some regional center. In historical-aesthetic purposes, the sequence of colors of visited roads is written in Chronicles. The red road is denoted by character '\textbf{0}', and the blue road is denoted by '\textbf{1}', so the result is a sequence of \textbf{L} binary digits. Young Martian Vasja studies history. Recently he found some parts of Chronicles describing the period of ruling of the King Ares. Vasja discovered the following requirement that should have been satisfied by the King. Each year the King must choose a new route, the sequence of which is greater than the corresponding one for previous year. When comparing, sequences are interpreted as binary numbers with leading zeros allowed. In the first year of his ruling the King was allowed to choose any route he wished. If the King is unable to find the route, he must finish his ruling. Vasja also discovered that Ares was very smart and he always chose such routes that maximized the length of his ruling period. Since Vasja has only parts of Chronicles, he cannot answer some questions. For example: - Which was King's route in \textbf{K}-th year of his ruling (years of ruling are enumerated starting from \textbf{1})? - In which year Ares chose a route denoted by a given sequence \textbf{S}? - Which route he chose after the route denoted by a given sequence \textbf{S}? - Which route was chosen before the route denoted by a sequence \textbf{S}? Vasja is not so smart as Ares so he asks you to answer the questions mentioned. Write a program that answers them. : \textbf{Input} The first line of the input contains five integers \textbf{N}, \textbf{M}, \textbf{F}, \textbf{L}, \textbf{Q} - the number of cities, roads, regional centers; the length of King's route and the number of Vasja's questions (\textbf{1} <= \textbf{N} <= \textbf{50}, \textbf{1} <= \textbf{M} <= \textbf{100S}, \textbf{1} <= \textbf{F} <= \textbf{N}, \textbf{1} <= \textbf{L} <= \textbf{60}, \textbf{1} <= \textbf{Q} <= \textbf{10 000}). The cities are enumerated with integers from \textbf{1} to \textbf{N}. The capital has number \textbf{1}. The following \textbf{M} lines describe the road system - three numbers in each line: \textbf{A_i}, \textbf{B_i} and \textbf{C_i}. Their meaning is that the \textbf{i}-th road is going from city number \textbf{A_i} to city number \textbf{B_i}, and its color is \textbf{C_i} ('\textbf{0}', if the road is red, '\textbf{1}', if it is blue). The next line contains \textbf{F} different integers - the numbers of cities, that are regional centers. The last \textbf{Q} lines contain one question each. The format of question description is the following: - \textbf{?} \textbf{K} - which route was chosen by the King in \textbf{K}-th year of his ruling (\textbf{1} <= \textbf{K} <= \textbf{5*10^18})? - \textbf{!} \textbf{S} - which year the King chose the route denoted by \textbf{S}? - \textbf{>} \textbf{S} - which route Ares chose after the route denoted by \textbf{S}? - \textbf{<} \textbf{S} - which route was chosen before the route denoted by \textbf{S}? The route is denoted by a sequence of \textbf{L} characters `\textbf{0}' and `\textbf{1}'. It is guaranteed that all questions are correct and the answer always exists. \textbf{Output} Output file must contain \textbf{T} lines, one for each question. For question \textbf{!} \textbf{S} it is required to output a single decimal integer. For all other questions the line must consist of \textbf{L} characters `\textbf{0}' and `\textbf{1}' - the record corresponding to the route.