Một con đường thẳng thường bị bão gây thiệt hại. Thiệt hại của mỗi cơn bão luôn nằm trong một đoạn liên tiếp. Dọc đường có \(k\) trạm quan sát, đánh số từ \(1\) đến \(k\) theo thứ tự từ một đầu đường.

Có ghi chép về \(n\) cơn bão, đánh số từ \(1\) đến \(n\) theo thời gian từ cũ đến mới. Cơn bão thứ \(i\) ảnh hưởng tất cả các trạm từ \(a_i\) đến \(b_i\), kể cả hai đầu.

Để nghiên cứu, cần trả lời \(m\) truy vấn: trạm \(p_j\) đã bị ảnh hưởng bởi bao nhiêu cơn bão có số thứ tự từ \(q_j\) đến \(r_j\)? Hãy trả lời từng truy vấn.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa \(n,m,k\), với \(1 \le n,m \le 100000\), \(1 \le k \le 1000000000\).

\(n\) dòng tiếp theo chứa \(a_i,b_i\), với \(1 \le a_i \le b_i \le k\).

\(m\) dòng cuối chứa \(p_j,q_j,r_j\), với \(1 \le p_j \le k\), \(1 \le q_j \le r_j \le n\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(m\) dòng theo thứ tự truy vấn. Dòng thứ \(j\) chứa số cơn bão từ \(q_j\) đến \(r_j\) đã ảnh hưởng trạm \(p_j\).

Chấm điểm

Giới hạn thời gian: \(2\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm; tổng cộng \(100\) điểm. \(10\%\) số điểm ứng với \(n,m,k \le 1000\); một phần \(30\%\) khác ứng với \(q_j=1\), \(r_j=n\) trong mọi truy vấn.

Ví dụ

3 3 10
1 7
5 10
3 5
1 1 1
5 1 3
5 2 3

1
3
2