LCC/Moose '20 Contest 4 S1 - All Hail!

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 0.5s
Memory limit: 64M

Problem type

As we all know, WLMOJistan, the nation governing the WLMOJistani people, has existed in some form or another since the dawn of mankind and as such has had countless rulers. For his Data Management final project, Theodore has decided to try and find the most accomplished ruler of WLMOJistan. To do this, he has found a list of all the accomplishments of WLMOJistani people and all the rulers of WLMOJistan. Using this data, can you help Theodore figure out which ruler has reigned over the most accomplishments?

Input Specification

The first line consists of a single integer N (1 \le N \le 10^4), the number of rulers of WLMOJistan.

The next N lines each consist of two integers s_i, e_i (-10^4 \le s_i \le e_i \le 10^4), the start and end years of the reign of the i^\text{th} ruler of WLMOJistan. The reigns of rulers will not overlap.

The next line consists of a single integer M (1 \le M \le 10^5), the number of accomplishments in the history of WLMOJistan.

The next M lines each consist of a single integer a (-10^4 \le a \le 10^4), representing that WLMOJistan had an accomplishment during the year a.

Output Specification

A single integer, the most accomplished ruler of WLMOJistan. It is guaranteed such a ruler will exist.

Note: If two rulers have the same number of accomplishments, pick the ruler who ruled for the shortest amount of time. If both quantities are identical, pick the ruler who began to rule the earliest.

Sample Input

22 24
19 20
17 18

Sample Output


Sample Illustration

Ruler Start of Reign End of Reign Number of Accomplishments
1 22 24 1
2 19 20 2
3 17 18 1

Noting that 4 achievements occur without WLMOJistan having a ruler in power.


There are no comments at the moment.