Tin tức trong lớp

Lớp 6B có $n$ học sinh, đánh số từ $1$ đến $n$. Mỗi học sinh $i$ có đúng một người bạn thân $g(i)$ mà cậu ấy sẽ gọi điện ngay khi biết một tin gì đó. Quan hệ này không đối xứng: $g(g(i))$ không nhất thiết bằng $i$, và $g(i)\ne i$.

Trong $m$ ngày liên tiếp, mỗi ngày có đúng một tin mới xuất hiện. Ngày thứ $i$, học sinh $a_i$ biết được một tin có độ hot $b_i$ ($b_i\ge 1$). Cậu lập tức gọi cho $g(a_i)$ và kể lại. Trong lúc kể, tin đã cũ đi một chút nên $g(a_i)$ chỉ nhận được tin với độ hot $b_i-1$. Người này lại làm điều tương tự, và cứ thế tiếp tục. Quá trình dừng lại khi độ hot chạm $0$, vì không ai buồn kể một tin có độ hot bằng $0$.

Nói chính xác hơn: nếu học sinh $x$ biết một tin với độ hot $y>0$ thì cậu gọi cho $g(x)$, và $g(x)$ biết tin đó với độ hot $y-1$; nếu $y-1>0$ thì $g(x)$ lại kể tiếp. Như vậy tin của ngày thứ $i$ được kể cho đúng $b_i$ học sinh, theo thứ tự

$$a_i,g(a_i),g(g(a_i)),\dots ,g^{b_i-1}(a_i)$$

Danh sách này có thể chứa những học sinh trùng nhau: trong cùng một ngày, một người có thể nghe đi nghe lại cùng một tin với các độ hot khác nhau.

Các giá trị $b_i$ được cho trực tiếp, còn $a_i$ được xác định qua dãy số nguyên $v_i$ theo công thức

$$a_i=((v_i+re{s}_{i-1}-1)modn)+1$$

trong đó $re{s}_0=0$ và $re{s}_i$ là số học sinh mà tin của ngày thứ $i$ là tin đầu tiên trong đời họ được nghe (tính trong suốt $m$ ngày đang xét). Nhiệm vụ của bạn là tính $re{s}_1,re{s}_2,\dots ,re{s}_m$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên $g(1),g(2),\dots ,g(n)$.
• Dòng thứ ba chứa $m$ số nguyên $v_1,v_2,\dots ,v_m$.
• Dòng thứ tư chứa $m$ số nguyên $b_1,b_2,\dots ,b_m$.

Dữ liệu ra

In ra $m$ dòng, dòng thứ $i$ chứa giá trị $re{s}_i$. Không in $re{s}_0$.

Ràng buộc

• $2\le n,m\le {10}^5$
• $1\le g(i)\le n$ và $g(i)\ne i$
• $1\le v_i\le {10}^7$
• $1\le b_i\le {10}^7$

Ví dụ