Giúp đỡ hoa lưu ly

Trong một buổi dạo vườn, FullHouse Dev phát hiện ra một khu vườn hoa lưu ly kỳ diệu. Người làm vườn đưa ra một bài toán thú vị về việc đếm số lượng hoa trong vườn. Với tinh thần nhiệt huyết, FullHouse Dev bắt đầu giải quyết câu đố này.

Bài toán

FullHouse Dev được cung cấp một mảng \(N\) số tự nhiên và cần xử lý các truy vấn sau:

• Truy vấn 0: Thay đổi giá trị tại vị trí \(i\) thành \(x\)
• Truy vấn 1: Đếm số lượng số chẵn trong đoạn từ \(l\) đến \(r\)
• Truy vấn 2: Đếm số lượng số lẻ trong đoạn từ \(l\) đến \(r\)

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\)
• Dòng thứ hai chứa \(N\) số tự nhiên
• Dòng thứ ba chứa số nguyên \(Q\) - số lượng truy vấn, theo sau là \(Q\) truy vấn có dạng:
  • 0 x y - thay đổi số tại vị trí x thành y
  • 1 x y - đếm số lượng số chẵn trong đoạn từ x đến y
  • 2 x y - đếm số lượng số lẻ trong đoạn từ x đến y

Ràng buộc:

• \(1 \leq N,Q \leq 10^5\)
• \(1 \leq l \leq r \leq N\)
• \(0 \leq A_i \leq 10^9\)
• \(1 \leq x \leq N\)
• \(0 \leq y \leq 10^9\)

Lưu ý: Chỉ số bắt đầu từ 1.

Ví dụ

INPUT

6
1 2 3 4 5 6
4
1 2 5
2 1 4
0 5 4
1 1 6

OUTPUT

2
2
4

Giải thích

• Truy vấn đầu tiên (1 2 5): Có 2 số chẵn trong đoạn từ 2 đến 5 (là 2 và 4)
• Truy vấn thứ hai (2 1 4): Có 2 số lẻ trong đoạn từ 1 đến 4 (là 1 và 3)
• Truy vấn thứ ba (0 5 4): Thay đổi số tại vị trí 5 thành 4
• Truy vấn thứ tư (1 1 6): Có 4 số chẵn trong đoạn từ 1 đến 6 (là 2, 4, 4, 6)