Thiên An và Tuyết Ny cùng đi du ngoạn sơn thủy trên một chiếc du thuyền tự động. Chiếc du thuyền này sẽ đưa họ đi thăm mạng lưới sông ngòi của đất nước Byteland, gồm tổng cộng \(N\) bến cảng được đánh số từ \(1\) đến \(N\), mỗi bến cảng có đúng một "bến cảng bên trái" và đúng một "bến cảng bên phải". Du thuyền của An và Ny xuất phát ở thành phố \(1\). Sau khi ghé thăm mỗi bến cảng, chiếc du thuyền này sẽ tự động rẽ sang "bến cảng bên trái" hoặc "bến cảng bên phải" của bến cảng hiện tại. Cụ thể, người ta đã lập trình sẵn một dãy gồm \(M\) chỉ thị L hoặc R (tương ứng với đích đến tiếp theo là bến cảng trái hoặc phải) cho chiếc du thuyền, và nó sẽ tự động thực hiện lặp lại dãy \(M\) chỉ thị này đúng \(K\) lần.

Bạn hãy lập trình dự đoán bến cảng cuối cùng mà An và Ny cập bến nhé!

Lưu ý: "Trái" và "phải" được bỏ vào ngoặc kép vì chỉ mang tính quy ước: bến cảng \(a\) nằm bên trái bến cảng \(b\) thì không nhất thiết bến cảng \(b\) phải nằm bên phải bến cảng \(a\).

Input

• Dòng đầu chứa ba số nguyên dương \(N\), \(M\) và \(K\) (\(1\leq N\leq 1000\), \(1\leq M\leq 500\), \(1\leq K\leq 10^9\)).

• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên tương ứng thể hiện lần lượt số hiệu của bến cảng bên trái và bên phải của bến cảng \(i\).

• Dòng cuối cùng chứa \(M\) ký tự (cách nhau bởi khoảng trắng) thể hiện dãy chỉ thị mà chiếc du thuyền được lập trình.

Output

• Một số nguyên duy nhất là số hiệu của bến cảng cuối cùng trong hành trình của An và Ny.

Example

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

4