Bạn đang chơi một trò chơi bao gồm \(n\) hành tinh. Mỗi hành tinh có một cổng dịch chuyển đến một hành tinh khác (hoặc chính hành tinh đó).

Bạn bắt đầu trên một hành tinh và sau đó đi qua các cổng dịch chuyển cho đến khi bạn đến một hành tinh mà bạn đã thăm trước đó.

Nhiệm vụ của bạn là tính toán cho mỗi hành tinh số lần dịch chuyển sẽ có nếu bạn bắt đầu trên hành tinh đó.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(q\): số lượng hành tinh và truy vấn. Các hành tinh được đánh số \(1,2,\ldots,n\)
• Dòng thứ hai có \(n\) số nguyên \(t_1,t_2,\ldots,t_n\): với mỗi hành tinh, điểm đến của của cổng dịch chuyển. Có thể là \(t_i=i\)

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq t_i \leq n\)

Output

• In \(n\) số nguyên theo đề bài

Example

5
2 4 3 1 4

3 3 1 3 4