410053: GYM103934 A The army of Thutmose III

Marcio "the indispensable" Himura is back in action. This time, he is investigating the administration of the Ancient Egypt during the reign of pharaoh Thutmose III. The organization Extraordinary Mystery Investigators (IME, in their language) has discovered ancient papyruses related to the Egyptian army. Thutmose was known for making his army march so often at regular intervals, that having local governors was unnecessary.

These papyruses have information regarding the construction of some buildings. In particular, they have the starting and finishing dates of the construction of each building. The ancient tales say that Thutmose chose certain days to march along with his army to supervise the construction of these buildings. In one day, they visited all the buildings that were under construction. A building was considered under construction since its starting date until its finishing date.

Marcio is studying how Thutmose III scheduled the marching days with his army. Regarding this schedule, Marcio has the following information. Since Thutmose was a careful person, he knows that each building was visited at least once. On the other hand, visiting a building many times intimidated the persons in charge of the construction. Therefore, the schedule of the army was planned in such a way to minimize the maximum number of days a single building is visited.

As a first step in his investigation, Marcio wants to find one such schedule. As Marcio is rusty after a two-year break, he needs your help in this task.

The first line contains an integer $$$N$$$ $$$(1 \leq N \leq 2500)$$$, the number of buildings. In this problem a date is represented by an integer such that a sequence of consecutive days corresponds to a sequence of consecutive integers. The following $$$N$$$ lines describe the buildings. The $$$i$$$-th line contains two integers, $$$s_i$$$ and $$$e_i$$$ ($$$-10^{18} \leq s_i < e_i \leq 10^{18}$$$), representing the starting and finishing dates, respectively, of the $$$i$$$-th building.

The first line contains an integer $$$M$$$, the number of days that the army marched. The following line contains $$$M$$$ integers indicating the dates the army marched. If multiple answers are possible, any of them will be accepted.

3
0 1
1 2
0 2

1
1

3
0 1
2 3
0 3

2
0 2