Dance Mooves

Farmer John’s cows are showing off their new dance mooves!

At first, all n cows stand in a line with cow i in the i-th position in line. The sequence of dance mooves is given by k pairs of positions (a[1], b[1]), (a[2], b[2]),...,(a[k], b[k]). In each minute i = 1..k of the dance, the cows in positions a[i] and b[i] in line swap. The same k swaps happen again in minutes k + 1 .. 2k, again in minutes 2k + 1 .. 3k, and so on, continuing in a cyclic fashion for a total of m minutes. In other words,

• In minute 1, the cows at positions a[1] and b[1] swap.

• In minute 2, the cows at positions a[2] and b[2] swap.

• ...

• In minute k, the cows in positions a[k] and b[k] swap.

• In minute k + 1, the cows in positions a[1] and b[1] swap.

• In minute k + 2, the cows in positions a[2] and b[2] swap.

• and so on ...

For each cow, please determine the number of unique positions in the line she will ever occupy.

Note: the time limit per test case on this problem is twice the default.

Input

The first line contains integers n (2 ≤ n ≤ 10^5), k (1 ≤ k ≤ 2 * 10^5) and m (1 ≤ m ≤ 10^18). Each of the next k lines contains (a[1], b[1])...(a[k], b[k]) (1 ≤ a[i] < b[i] ≤ n).

Output

Print n lines, where the i-th line contains the number of unique positions that cow i reaches.

Example

After 7 minutes, the cows in increasing order of position are [3, 4, 5, 2, 1, 6].

• Cow 1 reaches positions {1, 2, 3, 4, 5}.

• Cow 2 reaches positions {1, 2, 3, 4}.

• Cow 3 reaches positions {1, 2, 3}.

• Cow 4 reaches positions {2, 3, 4}.

• Cow 5 reaches positions {3, 4, 5}.

• Cow 6 never moves, so she never leaves position 6.

Examples