Một khu du lịch có ~n~ điểm tham quan, điểm ~i~ có trạm xe thứ ~i~, các trạm đánh số từ ~1~ đến ~n~. Từ trạm ~i~, có đúng một tuyến xe cố định đưa hành khách tới trạm ~t_i~ cho trước (nếu ~t_i=i~, nghĩa là điểm ~i~ là điểm tham quan cuối - xe không di chuyển đến điểm tham quan kế tiếp mà xe sẽ rời trạm ~i~ để đưa hành khách tham quan vòng quanh bên trong điểm tham quan này, sau mỗi chuyến xe lại quay lại trạm ~i~). Mỗi lần một chuyến xe nếu rời trạm ~i~, tại trạm ~i~ sẽ có thêm ~g_i~ hành khách mới lên xe (kể cả khi xe đi qua trạm ~i~ nhiều lần trong một hành trình dài).

Có ~q~ truy vấn, mỗi truy vấn cho hai số nguyên ~u,k~: nếu xuất phát từ trạm ~u~ (ban đầu xe không có khách, nếu rời trạm ~u~ thì xe sẽ nhận số hành khách đầu tiên là ~g_u~) và thực hiện đúng ~k~ chuyến liên tiếp. Hỏi sau ~k~ chuyến, xe đang ở trạm nào và đã đón được tổng cộng bao nhiêu hành khách?

Input

• Dòng 1: hai số nguyên ~n,q~ ~(1 \le n,q \le 2 \cdot 10^5)~;

• Dòng 2: ~n~ số nguyên ~t_1,\dots,t_n~ ~(1 \le i \le n; 1 \le t_i \le n)~;

• Dòng 3: ~n~ số nguyên ~g_1,\dots,g_n~ ~(1 \le i \le n; 1 \le g_i \le 10^9)~;

• ~q~ dòng tiếp theo, mỗi dòng hai số nguyên ~u,k~ ~(1 \le u \le n; 0 \le k \le 10^9)~.

Các số trên cùng một dòng được ghi cách nhau một dấu cách.

Output

Với mỗi truy vấn, in trên một dòng hai số nguyên: trạm đang đứng và tổng số hành khách đã đón - theo đúng thứ tự truy vấn trong dữ liệu vào.

Scoring

Sample Input 1

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

Sample Output 1

5 40

Notes

Xuất phát trạm ~1~. Chuyến ~1,\dots,4~ lần lượt đón ~1,2,3,4~ hành khách rồi tới trạm ~5~. Từ chuyến thứ ~5~ trở đi, xe di chuyển vòng quanh bên trong điểm ~5~ (vì ~t_5=5~) nhưng vẫn đi qua trạm ~5~, đón thêm ~g_5=5~ hành khách mỗi chuyến

• ~6~ chuyến còn lại (chuyến ~5~ đến ~10~) đón thêm ~6 \cdot 5=30~. Tổng cộng sau ~10~ chuyến: ~1+2+3+4+30=40~, xe đang ở trạm ~5~.