Зубробизон Ромалий выставил в ряд N горшков с травой и пронумеровал их слева направо числами от 1 до N.
Затем он составил M правил обмена, где каждое правило это два натуральных числа от 1 до N — номера горшков, которые нужно поменять местами.
В первый день он воспользовался первым правилом и поменял местами соответствующие горшки. Во второй день он воспользовался вторым правилом и поменял местами соответствующие горшки.
...
В M день он воспользовался M-м правилом и поменял местами соответствующие горшки.
В M + 1 день он воспользовался первым правилом и поменял местами соответствующие горшки.
Во M + 2 день он воспользовался вторым правилом и поменял местами соответствующие горшки.
И так далее...
Ромалий хочет проверить себя и просит вас рассчитать положение горшков через K дней.
В первой строке заданы три целых числа: N (1 ≤ N ≤ 103), M (1 ≤ M ≤ 105) и K (1 ≤ K ≤ 1018) — число горшков, число правил и количество дней соответственно.
Следующие M строк содержат описание правил в виде пары целых чисел ai и bi (1 ≤ ai, bi ≤ N), обозначающих номера горшков, которые нужно поменять местами.
В единственной строке выведите N чисел — положение горшков через K дней.
4 3 5
1 2
2 3
1 3
3 2 1 4
4 5 10
1 2
1 3
3 4
2 3
1 4
4 3 2 1
