There are x villages in Andhere Nagar. Each village has its index — an integer number from 1 to x. The capital has index a. All the roads in Andhere Nagar are two-way. The road system is such that there is exactly one path from the capital to each city, i.e. the road map looks like a tree. In Andhere Nagar's chronicles the road map is kept in the following way: for each village i, different from the capital, there is kept number p_i — index of the last village on the way from the capital to i.

Once the king of Andhere Nagar, Choupat Raja, decided to move the capital from village a to village b. Naturally, after this the old representation of the road map in Andhere Nagar 's chronicles became incorrect. Please, help the king find out a new representation of the road map in the way described above.

Input

The first line contains three space-separated integers x, a, b (2 ≤ x ≤ 5·10⁴, 1 ≤ a ≠ b ≤ n) — amount of villages in Andhere Nagar, index of the old capital and index of the new one, correspondingly.

The following line contains x - 1 space-separated integers — the old representation of the road map. For each city, apart from a, there is given integer p_i — index of the last city on the way from the capital to city i. All the cities are described in order of increasing indexes.

Output

Output x - 1 numbers — new representation of the road map in the same format.

Example 1

Input:
3 2 3
2 2

Output:
2 3

Example 2

Input:
6 2 4
6 1 2 4 2

Output:
6 4 1 4 2