Du Thuyền Xa Xỉ

Có $N$ cảng được đánh số từ $1$ đến $N$. Mỗi cảng có đúng hai con sông đi ra: một sông bên trái và một sông bên phải, mỗi sông dẫn đến một cảng khác (hoặc chính nó).

Xuất phát từ cảng số $1$, bạn đi theo một chuỗi $M$ hướng dẫn (mỗi hướng dẫn là L hoặc R), lặp lại đúng $K$ lần (tổng cộng $K\times M$ bước di chuyển).

Hãy xác định bạn kết thúc ở cảng nào.

Dữ liệu vào

• Dòng 1: Ba số nguyên $N$, $M$, $K$.
• $N$ dòng tiếp theo: Dòng $i+1$ chứa hai số nguyên là cảng đích khi đi theo sông trái và sông phải từ cảng $i$.
• Dòng cuối: $M$ ký tự cách nhau bởi dấu cách, mỗi ký tự là L hoặc R.

Dữ liệu ra

Một số nguyên duy nhất: số thứ tự cảng cuối cùng.

Ràng buộc

• $1\le N\le 1000$
• $1\le M\le 500$
• $1\le K\le {10}^9$

Ví dụ