Điệu nhảy bò (Gold)

Có $N$ con bò xếp thành một hàng tại các vị trí $1,2,\dots ,N$. Con bò đang đứng ở vị trí $i$ lúc ban đầu được gọi là con bò số $i$.

Buổi tập nhảy gồm $K$ động tác. Động tác thứ $j$ được cho bởi một cặp vị trí $(a_j,b_j)$: hai con bò đang đứng ở vị trí $a_j$ và vị trí $b_j$ đổi chỗ cho nhau.

Buổi nhảy kéo dài $M$ phút, mỗi phút thực hiện đúng một động tác. Các động tác được thực hiện lần lượt theo thứ tự $1,2,\dots ,K$ rồi lặp lại từ đầu cho đến khi hết $M$ phút, tức là ở phút thứ $t$ người ta thực hiện động tác thứ $((t-1)modK)+1$. Lưu ý rằng $M$ có thể nhỏ hơn $K$ (khi đó chỉ $M$ động tác đầu tiên được thực hiện), và $M$ cũng không nhất thiết chia hết cho $K$.

Với mỗi con bò, hãy đếm số vị trí phân biệt mà nó từng đứng trong suốt buổi nhảy, tính cả vị trí ban đầu của nó.

Dữ liệu vào

• Dòng đầu: ba số nguyên $N$, $K$, $M$.
• $K$ dòng tiếp theo: dòng thứ $j$ chứa hai số nguyên $a_j$ và $b_j$.

Dữ liệu ra

• $N$ dòng, dòng thứ $i$ chứa số vị trí phân biệt mà con bò số $i$ từng đứng.

Ràng buộc

• $2\le N\le {10}^5$
• $1\le K\le 2\times {10}^5$
• $1\le M\le {10}^{18}$
• $1\le a_j<b_j\le N$

Ví dụ