Program for a Psychological Survey of Programmers

Time limit2sMemory limit1024 MB

Summary

Given a keyword list and case/leading-digit rules, scan a program text and report the most frequent identifier, breaking ties by earliest first occurrence.

Level: Medium7 of 10
Topics: String, Hash map, Implementation, Simulation
Solved: No attempts yet

Problem

The company <> commissioned a famous psychologist to conduct a full psychological evaluation of all its employees. This psychologist is known for an innovative method that builds a complete psychological profile of an employee from the identifier that employee uses most often in programs. Unfortunately, the program used for the analysis was infected by a virus, so a new one must be written in a hurry. Help the famous psychologist. Write a program that, given a program, determines the identifier used most often in it.

Since different employees write programs in different programming languages, your program must work with an arbitrary language. Since different languages use different keywords, the list of keywords of the language being analyzed is provided in the input. Any sequence of Latin letters, digits, and underscores that is not a keyword and contains at least one character that is not a digit can be an identifier. In some languages an identifier may start with a digit, and in others it may not. If an identifier cannot start with a digit, a sequence that starts with a digit is not an identifier. In addition, you are told whether the language is case-sensitive with respect to the characters used in identifiers and keywords.

Input

The first line of the input contains the number $n$ , the number of keywords in the language ( $0 \le n \le 50$ ), and two words $c$ and $d$ , each of which is either <<yes>> or <<no>>. The word $c$ is <<yes>> if identifiers and keywords in the language are case-sensitive, and <<no>> if they are not. The word $d$ is <<yes>> if identifiers in the language may start with a digit, and <<no>> if they may not.

The next $n$ lines contain one word each, consisting of Latin alphabet letters and underscore characters: the keywords. All keywords are nonempty and distinct; if the language is not case-sensitive, they are distinct ignoring case as well. The length of each keyword does not exceed 50 characters.

After that, up to the end of the file, comes the program text. It contains only characters with ASCII codes from 32 to 126 and line breaks. The size of the input file does not exceed 10 kilobytes. The program contains at least one identifier.

Output

Output the identifier that occurs the maximum number of times in the program. If there are several such identifiers, output the one whose first occurrence is earliest. If the language given in the input is not case-sensitive, the identifier may be output in any case.

Examples4

Example 1

Input

0 yes no
int main() {
  int a;
  int b;
  scanf("%d%d", &a, &b);
  printf("%d", a + b);
}

Expected output

int

Example 2

Input

0 yes no
#define INT int
int main() {
  INT a, b;
  scanf("%d%d", &a, &b);
  printf("%d %d", a + b, 0);
}

Expected output

Example 3

Input

6 no no
program
var
begin
end
while
for
program sum;
var
  A, B: integer;
begin
  read(A, b);
  writeln(a + b);
end.

Expected output

Example 4
Input
```
1 yes yes
_
a = 0h
b = 0h
c = 0h
```
Expected output
```
0h
```