The Permian-Triassic extinction was Earth's most severe extinction event, resulting in the loss of $$$81$$$% of marine species and $$$70$$$% of terrestrial vertebrate species.
You have DNA data from $$$1 \le n \le 1000$$$ species that survived the event. Each DNA sequence is given as a binary string — a sequence of $$$0$$$s and $$$1$$$s — of length $$$1 \le l \le 32$$$. If a position contains $$$1$$$, that means the species has that gene; if it contains $$$0$$$, it doesn't.
During the extinction, a non-empty subset of genes was chosen (possibly all of them), and every species that had any of those genes went extinct.
You are now given DNA from $$$1 \le q \le 1000$$$ other species and must determine, for each, how the extinction might have affected it. You know there are three possible outcomes:
- "survives" — It can be proven the species would have survived
- "dies" — It can be proven the species definitely died
- "uncertain" — The results are inconclusive
The first line contains three integers: $$$n$$$, $$$q$$$, and $$$l$$$ — the number of known survivors, the number of species to test, and the length of each species' DNA string ($$$1 \le n, q \le 1000, 1 \le l \le 32$$$).
The next $$$n$$$ lines contain each of the DNA strings of the survivors. Each of the $$$q$$$ lines afterwards is a species' DNA whose outcome we wish to determine.
For each of the $$$q$$$ test species, output one of the following words on a new line: "survives", "dies", or "uncertain" (definitions above). Output is case-sensitive.
2 5 41100100010000100011000011111
survives survives uncertain uncertain dies
