Hành Tinh (Truy vấn I)

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $n$ hành tinh, mỗi hành tinh có một cổng dịch chuyển tức thời đến một hành tinh khác (có thể là chính nó). Cho $q$ truy vấn, mỗi truy vấn hỏi: xuất phát từ hành tinh $x$ , sau khi đi qua đúng $k$ cổng dịch chuyển, bạn sẽ đến hành tinh nào?

Dữ liệu vào

Dòng 1: hai số nguyên $n$ và $q$ .
Dòng 2: $n$ số nguyên $t_{1}, t_{2}, \dots, t_{n}$ — hành tinh đích của cổng dịch chuyển tại mỗi hành tinh.
$q$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $x$ và $k$ .

Dữ liệu ra

In $q$ số nguyên, mỗi số trên một dòng — hành tinh đến được sau $k$ bước dịch chuyển.

Ràng buộc

$1 \leq n, q \leq 2 \times 10^{5}$
$1 \leq t_{i} \leq n$
$1 \leq x \leq n$
$0 \leq k \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 3 2 1 1 4 1 2 3 4 4 1	1 2 4	Từ 1 qua 2 bước: 1→2→1. Từ 3 qua 4 bước: 3→1→2→1→2. Từ 4 qua 1 bước: 4→4.

Bình luận

Không có bình luận tại thời điểm này.