Khu du lịch Tam Chúc (Ba Sao Hà Nam) được mệnh danh là “Vịnh Hạ Long trên cạn”, nơi khoác lên mình vẻ đẹp ngút ngàn và đẹp như cõi mộng, nơi mà du khách sẽ cảm nhận được sự thuần khiết, thanh bình và yên ả. Quanh khu du lịch có rất nhiều địa điểm có thể khám phá như: Chùa Ngọc, Điện Tam Thế, Điện Pháp Chủ, Điện Quan Âm, Cổng Tam Quan, Phòng họp Quốc tế,… Giả sử có \(N\) điểm du lịch, tại một điểm bất kì có thể đi đến 2 địa điểm khác theo hướng trái L hoặc hướng phải R). Một tour du lịch cho khách sẽ xuất phát từ điểm 1, đi theo \(M\) chỉ dẫn chỉ gồm các ký tự L và R. Bé Bông lần đầu được đi du lịch ở Tam Chúc nên rất thích, mỗi tour du lịch bé muốn khám phá \(K\) lần. Vậy bạn hãy giúp mẹ bé tìm ra điểm dừng cuối cùng theo lộ trình bé Bông đã đi

Input

• Dòng đầu tiên ghi ba số nguyên dương \(N, M, K\) (\(N \le 10^3, M \le 5 \times 10^2, K \le 10^9\))
• \(N\) dòng tiếp theo, mỗi dòng ghi hai số nguyên là số hiệu của điểm tiếp theo nếu xuất phát từ điểm \(i\) đi theo hướng trái hoặc hướng phải.
• Dòng cuối cùng chứa \(M\) ký tự cách nhau bởi dấu trống chỉ gồm hai ký tự L và R là các chỉ dẫn của tour du lịch

Output

• Một số nguyên duy nhất là số hiệu của điểm dừng cuối cùng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(K \le 10^2\).
• Subtask \(2\) (\(40\%\) số điểm): \(K \le 10^5\);
• Subtask \(3\) (\(40\%\) số điểm): \(K \le 10^9\).

Example

4 3 3
2 4
3 1
4 2
1 3
L L R

4

4 3 3
2 4
3 1
4 2
1 3
L R R

2