Chắc nhiều bạn đã biết, ngoài niềm đam mê bất tận với trà sữa, GSPVH còn rất ham thích gắp thú bông. Đã thành thói quen, mỗi khi ghé thăm trung tâm thương mại, khu vui chơi hay công viên nào mà có máy gắp thú, GS ắt phải trổ tài với dăm ba đồng tiền lẻ. Nói là tiền lẻ thôi chớ đồng nào cũng màu hồng màu xanh cả. Trong cuộc sống hiện đại ngày nay, thú bông có nhiều lợi ích không thể nào bỏ qua. Những con gấu bông xinh xắn, dễ thương luôn khiến ai ai cũng cảm thấy nhẹ nhàng, êm ái mỗi khi ngắm nhìn chúng. Chúng giúp chúng ta xua tan bao áp lực bộn bề của cuộc sống vốn ngập tràn mỏi mệt. Nhiều chú gấu bông còn có cặp má phính véo thì thích miễn chê rồi. Vào mùa đông lạnh giá, gấu bông như chiếc lò sưởi giúp chúng ta ấm áp cả thể chất lẫn tinh thần. Chỉ cần dang rộng vòng tay ôm lấy một chú gấu bông to lớn, những đêm dài lạnh lẽo nơi Hà Nội chỉ 8 độ C sẽ là những giấc ngủ ngon trong chiếc mền ấm êm. Kể ra thì gấu bông cũng có nhiều cái hơn một số loài gấu khác ấy chứ nhỉ. Thứ nhất, gấu bông không khiến bạn phải lo “đau ví”. Một khi đã gắp về rồi thì gấu sẽ luôn tươi tắn, vui cười và cặp má thì lúc nào cũng bầu bĩnh; trong khi với một số loài gấu khác, nếu không được chăm bón bằng trà sữa, bỏng ngô CGV và bổ sung vitamin hẹn hò thường xuyên, gấu sẽ chuyển sang chế độ cau có, giận dỗi. Và tất nhiên, chi phí cho trà sữa hay sweetbox này tốn hơn xèng gắp gấu bông từ máy rất nhiều. Như đã nói ở trên, trong đêm đông giá lạnh, gấu bông sẽ là nguồn nhiệt sưởi ấm tấm lòng, ấy nhưng, nếu ôm một số loài gấu khác, có khi bạn sẽ còn lạnh hơn ấy chứ. Và quan trọng nhất, ngôn ngữ của loài gấu bông không có những từ “phụ tình”, “phổi bạn” hay “thay lòng đổi dạ”. Gấu bông luôn sẵn sàng ở bên bạn mãi mãi, chứ ở một số loài gấu khác thì lắm lúc không phải như vậy.

Thôi nào, cuộc chia tay của những chú/con gấu không làm bằng bông thì hãy còn nhiều lắm. Giờ hãy quay về với cửa hàng gắp thú ưa thích của GSPVH đã.

Khu vui chơi tại chợ đêm Oileh ở quận Chải Hâu có một chiếc máy gắp thú với vô vàn con thú bông sặc sỡ. Để tri ân những tín đồ mê gắp thú và truyền cảm hứng gắp thú bông cho thế hệ Z, chợ đêm Oileh tung ra một chương trình ưu đãi hấp dẫn. Theo đó, giá mỗi lượt chơi gắp thú được mô tả bởi hai dãy số nguyên dương \((s_{1}, s_{2}, \ldots, s_{n})\) và \((p_{0}, p_{1}, \ldots, p_{n})\). Giả sử \(\sigma\) là số tiền người chơi đã chi cho việc gắp thú trước đây, chi phí của lượt gắp thú kế tiếp được xác định như sau:

• Nếu \(0\leq \sigma < s_{1}\), giá tiền là \(p_{0}\).
• Nếu \(s_{1} \leq \sigma < s_{2}\), giá tiền là \(p_{1}\).
• Nếu \(s_{2} \leq \sigma < s_{3}\), giá tiền là \(p_{2}\).
• \(\ldots\)
• Nếu \(s_{(n - 1)} \leq \sigma < s_{n}\), giá tiền là \(p_{(n - 1)}\).
• Nếu \(s_{n} \leq \sigma\), giá tiền là \(p_n\).

Hai dãy số này thoả mãn các điều kiện \(s_{1} < s_{2}< \cdots < s_{n}\) và \(p_{0} > p_{1} > p_{2} > \ldots > p_{n}\), ý tưởng là nếu bạn gắp thú càng nhiều, lượt gắp thú tiếp theo sẽ càng rẻ.

Ví dụ, giả sử \(n = 3\) và \((s_{1}, s_{2}, s_{3}) = (20, 30, 40)\) và \((p_{0}, p_{1}, p_{2}, p_{3}) = (7, 5, 3, 2)\); giá mỗi lượt gắp thú như sau:

• Lượt gắp thú đầu tiên có giá \(p_0 = 7\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 7 < s_{1} = 20\).
• Lượt gắp thú thứ hai có giá \(p_{0} = 7\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 14 < s_{1} = 20\).
• Lượt gắp thú thứ ba có giá \(p_{0} = 7\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 21 < s_{2} = 30\).
• Lượt gắp thú thứ tư có giá \(p_{1} = 5\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 26 < s_{2} = 30\).
• Lượt gắp thú thứ năm có giá \(p_{1} = 5\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 31 < s_{3} = 40\).
• Lượt gắp thú thứ sáu có giá \(p_{2} = 3\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 34 < s_{3} = 40\).
• Lượt gắp thú thứ bảy có giá \(p_{2} = 3\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 37 < s_{3} = 40\).
• Lượt gắp thú thứ tám có giá \(p_{2} = 3\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 40 = s_{3}\).
• Kể từ lượt gắp thú thứ chín, giá mỗi lượt là \(p_{3} = 2\).

Trong máy gắp thú có một số con gấu bông. Mỗi con gấu bông có một giá trị riêng. Số lượng và giá trị của những con gấu bông bên trong máy được mô tả bởi \(m\) cặp số nguyên \((l_{1}, r_{1}), (l_{2}, r_{2}), \ldots, (l_{m}, r_{m})\) với ý nghĩa: Với mỗi bộ số \((i, j)\) thoả mãn \(1 \leq i \leq m\) và \(l_{i} \leq j \leq r_{i}\), trong máy có thêm một con gấu bông với giá trị \(j\). Chú ý rằng, nếu có nhiều bộ số \((i, j)\) với cùng một giá trị \(j\) thoả mãn các điều kiện ở trên, trong máy sẽ có nhiều con gấu cùng giá trị. Như vậy, tổng số gấu bông trong máy là \((r_{1} - l_{1} + 1) + (r_{2} - l_{2} + 1) + \cdots + (r_{m} - l_{m} + 1)\).

Ví dụ, giả sử \(m = 3\) và các bộ số lần lượt là \((2, 5), (8, 10), (10, 12)\). Khi đó, máy gồm 10 con gấu bông với giá trị lần lượt là \(2, 3, 4, 5, 8, 9, 10, 10, 11, 12\).

Với kinh nghiệm chinh chiến ở muôn vàn đấu trường gắp thú trên khắp mọi miền tổ quốc, GSPVH tự tin mình có thể gắp “bách phát bách trúng” (gắp phát nào trúng phát đó). Thế nhưng, để tránh việc nhân viên siêu thị phát hiện tài năng của GSPVH và đẩy GS ra xa đàn gấu thân yêu, GS luôn chọn gắp thú theo thứ tự giá trị từ nhỏ đến lớn. Nói cách khác, GS luôn chọn gắp con thú có giá trị nhỏ nhất trong số những con thú còn trong máy.

GSPVH đặt ra mục tiêu kiếm được số tiền \(t\) nhờ việc bán gấu gắp được (do nhà GS đã có đầy đủ gấu để ohm rùi). Do GS còn bận chuẩn bị đề thi PVHOI 3.0, GS muốn biết cần ít nhất bao nhiêu lượt gắp để số tiền kiếm được là ít nhất \(t\) (nói cách khác, tổng giá trị của những chú gấu gắp được trừ đi số tiền bỏ ra để chơi gắp thú không bé hơn \(t\)).

Để tăng độ khó cho bài toán, bạn được cho \(q\) số nguyên dương \(t_{1}, t_{2}, \ldots, t_{q}\). Với mỗi số \(t_{i}\), hãy bạn cần cho GS biết số lần chơi gắp thú ít nhất để thu về được số tiền không ít hơn \(t_{i}\).

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m\) và \(q\) \((1 \leq n, m, q \leq 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên \(s_{1}, s_{2}, \ldots, s_{n}\) \((0 < s_{1} < s_{2} < \ldots < s_{n} < 4 \cdot 10^{18} + 1)\).
• Dòng thứ ba chứa \(n + 1\) số nguyên \(p_{0}, p_{1}, p_{2}, \ldots, p_{n}\) \((4 \cdot 10^{18} + 1 > p_{0} > p_{1} > p_{2} > \ldots > p_{n} > 0)\).
• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(l_{i}\) và \(r_{i}\) \((1 \leq l_{i} \leq r_{i} \leq 10^{7})\).
• Dòng cuối cùng chứa \(q\) số nguyên \(t_{1}, t_{2}, \ldots, t_{q}\) \((1 \leq t_{i} \leq 4 \cdot 10^{18})\).

Output

• Gồm một dòng duy nhất chứa \(q\) số nguyên, số thứ \(i\) trong đó là số lượt chơi tối thiểu để GS kiếm đượt số tiền không ít hơn \(t_{i}\). Nếu GS gắp hết toàn bộ thú trong máy mà vẫn không kiếm đủ số tiền như mục tiêu, in ra \(-1\).

Scoring

• Subtask \(1\) (\(13\) điểm): \(m = n = 1\), \(q \leq 1000\) và \(r_{1} \leq 1000\).
• Subtask \(2\) (\(13\) điểm): \(m = n = 1\).
• Subtask \(3\) (\(13\) điểm): \(n = 1\).
• Subtask \(4\) (\(13\) điểm): \(n \leq 10\).
• Subtask \(5\) (\(18\) điểm): Không có ràng buộc gì thêm.

Example

3 3 3
20 30 40
7 5 3 2
2 5
8 10
10 12
1 20 34

7 9 -1