Robert đang thiết kế một trò chơi máy tính mới. Trò chơi gồm một anh hùng, \(n\) đối thủ và \(n+1\) ngục tối. Các đối thủ được đánh số từ \(0\) đến \(n-1\), còn các ngục tối được đánh số từ \(0\) đến \(n\). Đối thủ \(i\) (\(0\le i\le n-1\)) ở trong ngục tối \(i\) và có sức mạnh \(s[i]\). Không có đối thủ nào trong ngục tối \(n\).

Anh hùng bắt đầu bằng việc đi vào ngục tối \(x\) với sức mạnh \(z\). Mỗi khi anh hùng đi vào một ngục tối \(i\) (\(0\le i\le n-1\)), anh hùng đối đầu với đối thủ \(i\) và một trong các tình huống sau xảy ra:

• Nếu sức mạnh của anh hùng lớn hơn hoặc bằng sức mạnh \(s[i]\) của đối thủ, anh hùng thắng. Sức mạnh của anh hùng tăng thêm \(s[i]\) (\(s[i]\ge 1\)). Sau đó, anh hùng đi vào ngục tối \(w[i]\) (\(w[i]>i\)).
• Ngược lại, anh hùng thua. Sức mạnh của anh hùng tăng thêm \(p[i]\) (\(p[i]\ge 1\)). Sau đó, anh hùng đi vào ngục tối \(l[i]\).

Lưu ý rằng \(p[i]\) có thể nhỏ hơn, bằng hoặc lớn hơn \(s[i]\). Tương tự, \(l[i]\) có thể nhỏ hơn, bằng hoặc lớn hơn \(i\). Bất kể kết quả đối đầu, đối thủ vẫn ở trong ngục tối \(i\) và giữ nguyên sức mạnh \(s[i]\).

Trò chơi kết thúc khi anh hùng đi vào ngục tối \(n\). Có thể chứng minh rằng trò chơi kết thúc sau một số hữu hạn lần đối đầu, bất kể ngục tối bắt đầu và sức mạnh ban đầu của anh hùng.

Robert nhờ bạn kiểm thử trò chơi bằng cách chạy \(q\) lần mô phỏng. Với mỗi lần mô phỏng, Robert cho ngục tối bắt đầu \(x\) và sức mạnh ban đầu \(z\). Nhiệm vụ của bạn là tìm sức mạnh của anh hùng khi trò chơi kết thúc trong mỗi lần mô phỏng.

Chi tiết cài đặt

Bạn cần cài đặt các hàm sau:

void init(int n, std::vector<int> s, std::vector<int> p,
          std::vector<int> w, std::vector<int> l);

• n: số đối thủ.
• s, p, w, l: các mảng độ dài \(n\). Với mỗi \(0\le i\le n-1\):
  • \(s[i]\) là sức mạnh của đối thủ \(i\), cũng là lượng sức mạnh anh hùng nhận thêm sau khi thắng đối thủ \(i\).
  • \(p[i]\) là lượng sức mạnh anh hùng nhận thêm sau khi thua đối thủ \(i\).
  • \(w[i]\) là ngục tối anh hùng đi vào sau khi thắng đối thủ \(i\).
  • \(l[i]\) là ngục tối anh hùng đi vào sau khi thua đối thủ \(i\).
• Hàm này được gọi đúng một lần, trước mọi lời gọi tới simulate dưới đây.

long long simulate(int x, int z);

• x: ngục tối đầu tiên anh hùng đi vào.
• z: sức mạnh ban đầu của anh hùng.
• Hàm cần trả về sức mạnh của anh hùng khi trò chơi kết thúc, với giả thiết anh hùng bắt đầu bằng việc đi vào ngục tối \(x\) với sức mạnh \(z\).
• Hàm này được gọi đúng \(q\) lần.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): n q.
• Dòng \(2\): \(s[0]\ s[1]\ \ldots\ s[n-1]\).
• Dòng \(3\): \(p[0]\ p[1]\ \ldots\ p[n-1]\).
• Dòng \(4\): \(w[0]\ w[1]\ \ldots\ w[n-1]\).
• Dòng \(5\): \(l[0]\ l[1]\ \ldots\ l[n-1]\).
• Dòng \(6+i\) (\(0\le i\le q-1\)): x z cho lời gọi simulate thứ \(i\).

Dữ liệu ra

Trình chấm mẫu in câu trả lời theo định dạng sau:

• Dòng \(1+i\) (\(0\le i\le q-1\)): giá trị trả về của lời gọi simulate thứ \(i\).

Ràng buộc

• \(1\le n\le 400\,000\).
• \(1\le q\le 50\,000\).
• \(1\le s[i],p[i]\le 10^7\) với mọi \(0\le i\le n-1\).
• \(0\le l[i],w[i]\le n\) với mọi \(0\le i\le n-1\).
• \(w[i]>i\) với mọi \(0\le i\le n-1\).
• \(0\le x\le n-1\).
• \(1\le z\le 10^7\).

Phân nhóm

Ví dụ

3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3

24
25

init(3, [2, 6, 9], [3, 1, 2], [2, 2, 3], [1, 0, 1])

Nguồn

IOI 2021, Ngày 2 — Dungeons Game (dungeons).