#117. Vòng quay thử thách (CHALLENGE)

Trong một chương trình trò chơi truyền hình thực tế, người chơi phải đối mặt với một "Vòng quay thử thách" khổng lồ. Vòng quay được chia thành ô, đánh số từ đến theo chiều kim đồng hồ. Ô số nằm ngay sau ô số , tạo thành một vòng khép kín.

Tại mỗi ô thứ , ban tổ chức quy định hai chỉ số:

• : Ngưỡng điểm thử thách. Để được tham gia chơi tại ô này, người chơi phải có số điểm hiện tại ít nhất là .
• : Điểm thưởng. Sau khi hoàn thành thử thách tại ô này, số điểm của người chơi sẽ tăng thêm .

Trò chơi diễn ra liên tục với các sự kiện thay đổi luật chơi từ ban tổ chức hoặc các lượt chơi thử nghiệm. Có sự kiện thuộc 3 loại sau:

1. Thay đổi độ khó (): Ban tổ chức thay đổi Ngưỡng điểm thử thách tại ô thành (tức là gán ).

2. Thay đổi phần thưởng (): Ban tổ chức thay đổi Điểm thưởng tại ô thành (tức là gán ).

3. Lượt chơi thử (): Một người chơi muốn bắt đầu từ ô , đi theo chiều kim đồng hồ và kết thúc ngay sau khi hoàn thành ô . Hãy tính số điểm ban đầu nhỏ nhất cần chuẩn bị để người chơi có thể vượt qua tất cả các ô trong hành trình đó mà không bị loại (luôn thỏa mãn điều kiện điểm tại mọi ô đi qua).

Quy ước hành trình:

• Nếu : Người chơi đi qua các ô .
• Nếu : Người chơi đi qua các ô .

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên và .
• Dòng thứ hai chứa số nguyên .
• Dòng thứ ba chứa số nguyên .
• dòng tiếp theo, mỗi dòng mô tả một sự kiện theo định dạng: loại u v.
  • Với loại 1 và 2: , .
  • Với loại 3: .

Kết quả:

• Với mỗi sự kiện loại 3, in ra một số nguyên duy nhất là số điểm ban đầu nhỏ nhất cần thiết.

Ví dụ:

Dữ liệu:

4 5
3 5 4 1
2 1 3 2
3 1 3
3 3 1
1 2 10
2 1 5
3 1 3

Kết quả:

3
4
5

Giới hạn:

• Subtask #1 (20% số điểm): .
• Subtask #2 (20% số điểm): Không có sự kiện loại 1 và 2.
• Subtask #3 (20% số điểm): Không có sự kiện loại 2.
• Subtask #4 (20% số điểm): Không có sự kiện loại 1.
• Subtask #5 (20% số điểm): Không có ràng buộc bổ sung.