Monkey Poo

Problem Statement

You are analysing a monkey which is sitting on a line, it is at point $x$ on the line and is throwing poo left and right onto other points.

You wish to know how much poo the monkey is throwing, so you have set up $k$ buckets along the line, which cover some sections of the line, the $i^{th}$ bucket covers all points from $l_i$ to $r_i$ inclusive.

You are going to go in your rover to pick up the poo, but you need to know how much poo the buckets have caught. To measure this, you set up a radar on the monkey which outputs the distance from the monkey that the monkey threw the poo, however you forgot to measure weather the poo goes left or right! This means you don't know if it lands in one of your buckets or not.

Output the maximum and the minimum amount of poo you could have gotten in the buckets given the information from the radar.

Input Format

Your first line will contain three space-separated integers $n$, $x$ and $k$, representing the number of radar measurements, the point of the monkey and the number of buckets you set up respectively.

Your next line will contain $n$ non-negative integers, the $i^{th}$ of which represents the distance that the $i^{th}$ piece of poo the monkey threw travelled.

Your next $k$ lines will contain two integers each, the $i^{th}$ of which will contain $l_i$ and $r_i$ which is the interval the $i^{th}$ bucket covers.

Output Format

You should output a single line containing two space-separated integers, the first being the maximum amount of poo that could have been collected in the buckets and the second being the minimum amount of poo that could have been collected in the buckets.

Constraints

• $1 \leq n, x, k \leq 10^5$
• $1 \leq l_i, r_i \leq 10^5$
• $1 \leq \text{poo radar distance} \leq 10^5$

Sample Cases

10 10 3
0 1 2 3 4 5 6 7 8 9
1 4
18 20
7 10

8 3

Explanation 1

Notice the poos that are thrown a distance $0$, $8$ and $9$ must land in a bucket (for example the poo thrown a distance $0$ will land in the $3^{rd}$ bucket as it will land on point $10$), therefore at least $3$ poos will be caught.

In a similar way, buckets $0$, $1$, $2$, $3$, $6$, $7$, $8$ and $9$ may or may not land in a bucket depending on if they're thrown left or right, therefore there is a maximum of $8$ poos that can be caught potentially.

3 10 2
5 9 3
1 2
1 3 

1 0

1 100000  1
99999
1 1

1 0

Template

n, x, k = map(int, input().split())
poo_distances = list(map(int, input().split()))
buckets = [tuple(map(int, input().split())) for _ in range(k)] # list of tuples [(l_1, r_1), (l_2, r_2), ...]

# print your output