Giải bài trực tuyến

Cho N số nguyên (có thể âm, N ≤ 1000). Các số được đánh số từ 0 đến N-1, số thứ i được ký hiệu là A(i). Mỗi số có không quá 1000 chữ số. Bạn cần trả lời Q truy vấn (Q ≤ 10⁵). Mỗi truy vấn có dạng: X₁ Y₁ C₁ X₂ Y₂ C₂, trong đó:

• X₁, Y_1, X₂, Y₂ là các số nguyên nằm trong khoảng [0, N-1].
• C₁, C₂ là các phép toán, có thể là +, - hoặc *

Nhiệm vụ của bạn là kiểm tra A(X₁) C₁ A(Y₁) có bằng A(X₂) C₂ A(Y₂) có bằng nhau hay không. Ví dụ:

• N = 3
• Dãy số: 10 20 30
• Truy vấn: 0 2 + 1 1 +
• Bạn cần kiểm tra A(0) + A(2) có bằng A(1) + A(1) hay không.

Input

• Dòng đầu chứa 2 số nguyên dương N, Q.
• N dòng tiếp theo, dòng thứ i chứa số nguyên A(i).
• Q dòng tiếp theo, mỗi dòng chứa X₁, Y₁, C₁, X₂, Y₂, C₂ mô tả truy vấn.

Output

Gồm Q dòng, mỗi dòng in ra YES nếu 2 số bằng nhau, và NO nếu 2 số khác nhau.

Giới hạn

• Có 40% số test N ≤ 500, Q ≤ 5000, mỗi số trong input không quá 100 chữ số
• Trong tất cả các test N ≤ 1000, Q ≤ 100,000; mỗi số trong input không quá 1000 chữ số
• Thời gian chạy cho mỗi test: 1s, riêng test đề bài có giới hạn thời gian chạy là 0.5s.

Chú ý:

• Trong thời gian thi, bài của bạn chỉ được chấm với test đề bài.
• Nếu bài của bạn chạy đúng trên máy mình, nhưng sai khi nộp lên SPOJ, bạn có thể kiểm tra ở ideone. Chú ý khi submit lên ideone, để chế độ Secret để người khác không đọc được code của bạn.

Example

Input:

4 3
1
2
3
4
0 1 - 2 3 -
0 3 + 1 2 +
0 3 * 1 2 *

Output:
YES
YES
NO