Chinese ID Number

Interview

Time limit2sMemory limit512 MB

Summary

Check an 18-character Chinese ID: region code from a given list, birthday in 1900 to 2011, sequence code not 000, then for valid IDs report gender by odd/even sequence code. The checksum is a mod 11 weighted sum of the first 17 digits plus a digit x making the total 1, with x=10 written as 'X'.

Level: Medium6 of 10
Topics: String, Array, Math, Implementation
Solved: No attempts yet

Problem

Every citizen of China has an ID number. An ID number has 18 characters. The first 17 characters are digits, and the last character is either a digit or 'X'.

The first 17 characters are split into 3 consecutive parts. Each part, in order, represents the region code, the birthday code, and the sequence code.

The region code is 6 characters long. The valid region codes are predetermined by the government, and any 6-character code not on that list is not a valid region code.
The birthday code is 8 characters long and has the form YYYYMMDD. The first 4 characters are the year, the next 2 are the month, and the last 2 are the day.
- If the month or day is a single-digit number, pad it with a leading 0 to make it two digits.
- A valid birthday code must represent a date between January 1, 1900 and December 31, 2011.
The sequence code is a 3-digit number. The 3-digit number is chosen arbitrarily, and "000" is not allowed. Every other number is a valid sequence code. An odd sequence code means male, and an even one means female.

The last character of the ID number is the checksum code, and it must be computed with a formula. Let the first 17 digits of the ID number be A1, A2, ..., A17. Compute the checksum code with the equation below.

x + A1×2^17 + A2×2^16 + A3×2^15 + ... + A16×2^2 + A17×2^1 ≡ 1 (mod 11)

Exactly one x satisfies the equation above. If x is 10, the checksum code is 'X'; otherwise x is the checksum code.

Given one ID number and a list of valid region codes, write a program that determines whether the ID number is valid, and if it is valid, whether the person is male or female.

Input

The first line gives an ID number. The ID number has 18 characters; the first 17 consist only of the digits 0 through 9. The last character is either a digit from 0 to 9 or 'X'.

The second line gives N (1 ≤ N ≤ 50), the number of valid region codes.

Each of the next N lines gives one valid region code. A region code has 6 characters and consists only of the digits 0 through 9. It does not start with 0. The region codes in the input are distinct.

Output

If the ID number given in the input is not valid, print "I". If it is valid and the person is male, print "M"; if female, print "F".

Examples5

Example 1
Input
```
441323200312060636
1
441323
```
Expected output
```
M
```
Example 2
Input
```
62012319240507058X
1
620123
```
Expected output
```
F
```
Example 3
Input
```
321669197204300886
2
610111
659004
```
Expected output
```
I
```
Example 4
Input
```
230231198306900162
1
230231
```
Expected output
```
I
```
Example 5
Input
```
341400198407260005
1
341400
```
Expected output
```
I
```