Dọc theo một con đường chạy theo hướng đông-tây, có \(A\) đền thờ và \(B\) chùa. Đền thờ thứ \(i\) từ phía tây cách đầu đường phía tây \(s_i\) mét và chùa thứ \(i\) từ phía tây cách đầu đường phía tây \(t_i\) mét.

Trả lời các truy vấn \(Q\) sau đây:

Truy vấn thứ \(i (1 \leq i \leq Q)\): Nếu bắt đầu từ một điểm cách đầu đường phía tây \(x_i\) mét và di chuyển tự do dọc theo con đường, khoảng cách tối thiểu cần đi để thăm một đền thờ và một chùa là bao nhiêu? (Được phép đi qua nhiều đền thờ và chùa hơn yêu cầu.)

Ràng buộc

• \(1 \leq A, B \leq 10^5\)
• \(1 \leq Q \leq 10^5\)
• \(1 \leq s_1 < s_2 < \ldots < s_A \leq 10^{10}\)
• \(1 \leq t_1 < t_2 < \ldots < t_B \leq 10^{10}\)
• \(1 \leq x_i \leq 10^{10}\)
• Các giá trị \(s_1, \ldots, s_A, t_1, \ldots, t_B, x_1, \ldots, x_Q\) đều khác nhau.
• Tất cả giá trị đầu vào là số nguyên.

INPUT FORMAT

• Dòng đầu tiên chứa ba số nguyên \(A\), \(B\), và \(Q\).
• \(A\) dòng tiếp theo mỗi dòng chứa một số nguyên biểu thị vị trí của một đền thờ.
• \(B\) dòng tiếp theo mỗi dòng chứa một số nguyên biểu thị vị trí của một chùa.
• \(Q\) dòng cuối cùng, mỗi dòng chứa một số nguyên biểu thị khoảng cách từ điểm xuất phát đến đầu đường phía tây.

OUTPUT FORMAT

• In ra \(Q\) dòng, mỗi dòng chứa câu trả lời cho mỗi truy vấn.

Ví dụ:

Input

2 3 4
100
600
400
900
1000
150
2000
899
799

Output

350
1400
301
399

Giải thích ví dụ mẫu

Ví dụ 1:

• Input:

  2 3 4 100 600 400 900 1000 150 2000 899 799

• Giải thích:

  • Để thăm đền thờ ở 100 và chùa ở 400 từ điểm xuất phát 150, khoảng cách tối thiểu cần đi là 350 mét.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House