CleverRaccoon's Word Learning Schedule

CleverRaccoon follows the raccoon word forgetting curve and starts learning words from day \(1\). There are \(n\) words. Under normal circumstances, the \(i\)-th word is scheduled to be learned for the first time on day \(d_i\).

Additionally, each word has \(k\) review sessions. For the \(j\)-th review the review offset is given as \(t_j\). This means that normally, after the first time learning a word, its \(j\)-th review is scheduled on day \(d_i + t_j\). In other words, if a word is learned on day \(d_i\), its reviews are planned on days \(d_i + t_1, d_i + t_2, \ldots, d_i + t_k\) respectively.

However, there are \(m\) special days. The \(i\)-th special day is given as \(s_i\). On a special day, CleverRaccoon forgets to study entirely. Any learning or review scheduled on a special day is postponed by one day.

• If a word's first learning is postponed to the next day, then its review sessions are rescheduled based on the postponed learning day.
• If a review session is postponed to the next day, the subsequent review sessions remain scheduled based on the original learning day.
• If multiple events (learning or reviews) fall on the same day, they are all carried out (i.e. multiple events may occur in a single day).

CleverRaccoon wants to know:

• The total number of days required to finish learning and reviewing all words.
• The number of new words learned on each day.
• The number of reviews completed on each day.

inputFormat

The input begins with three integers \(n\), \(k\), and \(m\) separated by spaces.

The second line contains \(n\) integers: \(d_1, d_2, \ldots, d_n\) indicating the originally scheduled learning day for each word.

The third line contains \(k\) integers: \(t_1, t_2, \ldots, t_k\) specifying the review offsets.

The fourth line contains \(m\) integers: \(s_1, s_2, \ldots, s_m\) representing the special days during which no studying occurs.

outputFormat

On the first line, output a single integer representing the total number of days required to complete all learning and reviews.

Then output exactly that many lines. The \(i\)-th line (1-indexed) should contain two integers separated by a space: the number of new words learned on day \(i\) and the number of reviews conducted on day \(i\), respectively.

sample

2 2 1
1 2
1 2
2

5
1 0
0 0
1 2
0 1
0 1

</p>