Công ty Anpha có \(n\) người đánh số từ 1 tới \(n\), có \(1\) người là giám đốc, những người còn lại thì mỗi người chịu quản lý trực tiếp của một người khác. Người thứ \(u\) (\(1 \le u \le n\)) gọi là quản lý người thứ \(v\) (\(1 \le v \le n\)) nếu tồn tại dãy \(v = p_1, p_2, \ldots, p_k = u\) trong đó \(p_i\) (\(i = 1, 2, \ldots, k - 1\)) chịu sự quản lý trực tiếp của \(p_{i+1}\). Mỗi người được coi là quản lý chính họ. Giám đốc quản lý tất cả mọi người trong công ty.

Mỗi người có mức đóng góp nhất định cho công ty, người thứ \(i\) (\(1 \le i \le n\)) có mức đóng góp \(a_i\); không có hai người nào có mức đóng góp bằng nhau. Khả năng quản lý của một người \(u\) là giá trị nhỏ nhất trong các mức đóng góp của những người do \(u\) quản lý.

Ban đầu tất cả mọi người đều không đảm nhiệm công việc nào. Lần lượt \(m\) sự kiện xảy ra ở công ty, mỗi sự kiện thuộc \(1\) trong \(2\) loại:

• Loại 1: Có \(x\) công việc cần người đảm nhiệm, các công việc được giao lần lượt, từng công việc một. Việc giao mỗi công việc như sau: đầu tiên công việc được đưa tới giám đốc. Khi công việc được đưa tới người \(u\), nếu có \(1\) người chịu sự quản lý trực tiếp của \(u\) chưa đảm nhiệm công việc nào, \(u\) sẽ giao công việc cho người này; nếu có nhiều người chịu sự quản lý trực tiếp của \(u\) chưa đảm nhiệm công việc nào, \(u\) sẽ giao công việc cho người có khả năng quản lý nhỏ nhất. Người phải đảm nhiệm công việc là người bị giao việc và không có cấp dưới trực tiếp chưa có việc để giao. Bạn cần xác định người phải đảm nhiệm công việc thứ \(x\) trong sự kiện này;

• Loại 2: Người thứ \(y\) hoàn thành công việc (trở thành người không có việc), khi đó việc giao việc diễn ra như sau: nếu một người \(u\) không có việc và cấp trên trực tiếp của \(u\) đang đảm nhiệm việc thì cấp trên này sẽ giao việc mình đang đảm nhiệm cho \(u\). Bạn cần xác định số lượt giao việc trong sự kiện này.

Dữ liệu vào:

• Dòng 1: \(n, m\) là số người và số sự kiện \((n,m \le 10^5)\)
• Dòng 2: \(a_1, a_2, ..., a_n\) với \(a_i\) là mức đóng góp của người \(i\) \((1 \le a_i \le 10^9)\)
• Dòng 3: \(p_1, ..., p_n\) với p_i = 0 nghĩa là giám đốc, nếu \(p_i \neq 0\) thì \(p_i\) là cấp trên trực tiếp của \(i\) \((0 \le p_i \le n)\)
• Tiếp theo \(m\) dòng mô tả các sự kiện:
  • \(1\) \(x\) \((1 \le x \le n)\) mô tả sự kiện loại 1: có \(x\) công việc cần người đảm nhiệm (dữ liệu đảm bảo trước sự kiện có ít nhất \(x\) người chưa có việc)
  • \(2\) \(y\) \((1 \le y \le n)\): mô tả sự kiện loại 2: ngưới thứ \(y\) hoàn thành công việc (dữ liệu đảm bảo trước đó người \(y\) đảm nhận công việc).

Dữ liệu ra:

• Với mỗi sự kiện, ghi ra:
  • Sự kiện loại 1: số thứ tự người đảm nhận công việc cuối cùng
  • Sự kiện loại 2: số lượt giao việc

Input 1

8 4
1 3 5 7 9 10 11 12
0 1 2 3 2 3 5 5
1 8
2 4
2 6
2 7

Output 1

1
3
2
1

Giải thích:

• Công ty có \(8\) người, người \(1\) là giám đốc, trong sự kiện \(1\), có \(8\) công việc cần người đảm nhiệm nên người \(1\) đảm nhiệm công việc cuối cùng (công việc thứ \(8\));
• Sự kiện thứ \(2\): sau sự kiện \(1\) tất cả \(8\) người đều đang đảm nhận công việc. Khi người \(4\) hoàn thành công việc: người \(3\) giao việc của mình đang đảm nhiệm cho người \(4\), người \(2\) giao việc của mình đang đảm nhiệm cho người \(3\), người \(1\) giao việc của mình đang đảm nhiệm cho người \(2\). Có \(3\) lượt giao việc;
• Sự kiện thứ \(3\): sau sự kiện \(2\) người \(1\) không có việc. Khi người \(6\) hoàn thành công việc: người \(3\) giao việc cho người \(6\), người \(2\) giao việc cho người \(3\). Có \(2\) lượt giao việc;
• Sự kiện thứ \(4\): sau sự kiện \(3\) người \(1\) và \(2\) không có việc. Khi người \(7\) hoàn thành công việc: người 5 giao việc cho người \(7\). Có \(1\) lượt giao việc

Ràng buộc

• Subtask 1: 25% số test và số điểm có: mỗi người có 0 hoặc 2 cấp dưới trực tiếp, những người không có cấp dưới thì chịu sự quản lý của số lượng người như nhau;
• Subtask 2: 30% số test và số điểm có sau mỗi sự kiện loại 2 không có lượt giao việc nào;
• Subtask 3: 45% số test và số điểm không có giới hạn gì thêm.