Each item ID is an alphanumeric word. All IDs are unique.
Input:
Line 1 contains one integer N, where N is the number of items in the entire collection
(including the missing item).
This is followed by N lines, representing the original collection. Each line only consists of an item ID.
This is followed by another N-1 lines, representing the collection after removing one item. Each line consists of an item ID.
Output:
The item ID of the missing item.
Limits:
Subtask 1-4 Memory Limit: 24MB
Subtask 5-6 Memory Limit: 4MB
Subtasks:
Subtask 1 (5%): Numeric IDs only, N <= 10^4, maxID <= 16 million
Subtask 2 (5%): Numeric IDs only, N <= 10^6, maxID <= 16 million
Subtask 3 (10%): Numeric IDs only, N <= 10^6, maxID <= 64 million
Subtask 4 (25%): Numeric IDs only, N <= 10^6, maxID <= 2^32-1
Subtask 5 (30%): Numeric IDs only, N <= 10^6, maxID <= 2^32-1
Subtask 6 (25%): Alphanumeric IDs, N <= 10^6, max ID length <= 10 characters
Subtask 7 (0%): Sample Testcases
Sample Input 1:
9
41
37
34
30
20
13
100
4
55
13
30
55
37
41
4
34
20
Sample Output 1:
100
Sample Input 2:
8
40
39
27
88
42
14
94
63
40
27
88
63
14
42
94
Sample Output 2:
39
Sample Input 3:
10
9
93
100
30
6
85
13
83
51
34
6
13
30
9
34
100
85
93
51
Sample Output 3:
83