Problem Background

On August 17, 2023, at 21:44, the time limit for this problem was changed to 500 ms.

He closed his eyes, gazing at the words on the sandy ground.\
Phrases, recited day and night, flowing effortlessly from the pen; under the night sky, stars scattered like words.\
New ideas, almost within reach, yet still distant; sighs filled with near-success.\
She smiled with relief, stood up gracefully, and gently tapped his back.\
Amidst the flowing light, raccoon paws danced; in the night breeze, new words were sincere.\
"You did it..."\
An ordinary midsummer night, profound words.\
The efforts of memorization, twinkling like stars...

Problem Description

Little raccoon CleverRaccoon follows the raccoon's word forgetting curve, starting to memorize words from day 1.

There are a total of \( n \) words. Normally, the \( i \)-th word will be first learned on day \( d_i \).

Each word is scheduled for \( k \) reviews. For the \( j \)-th review, there is a review point \( t_j \), indicating that normally, each word will be reviewed \( t_j \) days after its first learning. In other words, the \( j \)-th review for the \( i \)-th word is scheduled for day \( d_i + t_j \).

Additionally, there are \( m \) days of special circumstances, with the \( i \)-th special circumstance occurring on day \( s_i \). On these days, CleverRaccoon forgets to memorize words, and any conflicting first learning or review times will be postponed to the next day.
- If the first learning time of a word is postponed to the next day, the word's reviews will be scheduled based on the postponed first learning time.
- If the current review time of a word is postponed to the next day, it will not affect the subsequent review times of that word.
- If multiple learning or review times coincide on the same day, multiple learning or reviews will be conducted on that day.

CleverRaccoon wants to know: the total number of days required to learn and review all words, the number of new words learned each day, and the number of words reviewed each day.

Input Format

The first line contains three integers \( n \), \( m \), and \( k \), representing the total number of words to be memorized, the number of special circumstance days, and the number of reviews each word requires, respectively.

The second line contains \( n \) integers \( d_i \), representing the first learning day for each word. It is guaranteed that \( d \) is monotonically non-decreasing.

The third line contains \( m \) integers \( s_i \), representing the special circumstance days. It is guaranteed that \( s \) is monotonically increasing. If \( m = 0 \), this line is omitted.

The fourth line contains \( k \) integers \( t_i \), representing the review points for all words. It is guaranteed that \( t \) is monotonically increasing.

Output Format

The first line contains one integer, representing the total number of days \( x \) required for CleverRaccoon to learn and review all words.

The next \( x \) lines contain two integers each, representing the number of new words learned and the number of words reviewed each day.

Sample Input and Output

Input Sample #1

5 0 2
1 1 1 2 3
1 2

Output Sample #1

5
3 0
1 3
1 4
0 2
0 1

Input Sample #2

5 1 2
1 1 1 2 3
1
1 2

Output Sample #2

5
0 0
4 0
1 4
0 5
0 1

Input Sample #3

5 1 3
1 2 3 4 5
3
1 2 3

Output Sample #3

8
1 0
1 1
0 0
2 4
1 3
0 3
0 3
0 1

Notes/Hints

Assume the input word numbers are sequentially numbered from \( 1 \) to \( n \).

Sample Explanation #1

Sample Explanation #2

Sample Explanation #3

Data Range

This problem uses Subtask-based testing.

For 100% of the data, it is guaranteed that \( 1 \leq n \leq 10^6 \), \( 0 \leq m \leq 200 \), \( 1 \leq k, d_i, t_i \leq 10^3 \), and \( s_m < d_n \). It is guaranteed that \( d \) is monotonically non-decreasing, and \( t \) and \( s \) are monotonically increasing.

见题面 Input 部分

见题面 Output 部分