Quốc lộ 1X


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

An đang chuẩn bị di chuyển trên QL 1X. Cậu sẽ xuất phát tại km số 0, lúc 0 phút. Tại km thứ 0 có một biển báo ghi tốc độ tối đa.

Ngoài ra trên đường đi có thêm $N$ biển thay đổi tốc độ đặt tại vị trí km số $a_1,a_2,...,a_N$. Thời gian cậu gặp biển $a_i$ là phút thứ $b_i$. Biết rằng, giữa hai biển báo bất kì, cậu đều duy trì một tốc độ không đổi. Tức là sau khi gặp biển báo thứ $i$, cậu sẽ đi với tốc độ ghi trên biển cho đến khi gặp biển $i+1$.

Cậu có $Q$ câu hỏi, cậu mất bao nhiêu phút (làm tròn xuống đến số nguyên gần nhất) để tới điểm km số $d$.

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên $N, Q \ (0< N,Q \le 10^5)$;
  • Dòng tiếp theo chứa $N$ số nguyên $a_i \ (0<a_1<a_2<...<a_N \le 10^9)$;
  • Dòng tiếp theo chứa $N$ số nguyên $b_i \ (0<b_1<b_2<...<b_N \le 10^9)$;
  • $Q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $d \ (0<d\le a_N)$.

Kết quả

  • In trên $Q$ dòng, mỗi dòng ghi một số nguyên là kết quả của câu hỏi tương ứng.

Chấm điểm

10;$N=1$. 20;$Q=1$. 30;$N,Q\le 10^3$. 40;Không có giới hạn gì thêm

Ví dụ

Ví dụ 1

input

2 4
4 10
4 7
6
4
2
7

output

5 4 2 5

Comments

There are no comments at the moment.