Cho hai xâu ký tự ~S~ và ~T~ cùng độ dài ~n~, chỉ chứa ~c~ chữ cái đầu tiên trong bảng chữ cái tiếng Anh viết thường (từ ký tự thứ 1 đến ký tự thứ ~c~). Một thao tác shift một ký tự là thay đổi ký tự đó thành ký tự kế tiếp trong bộ chữ cái ~c~ ký tự này. Cụ thể, nếu ký tự là ký tự thứ ~i~ ~(1 \le i < c)~, nó sẽ trở thành ký tự thứ ~i+1~. Nếu ký tự là ký tự thứ ~c~, nó sẽ quay trở lại thành ký tự thứ 1 (ví dụ với ~c=3~, ~'a' \rightarrow 'b'~, ~'b' \rightarrow 'c'~, ~'c' \rightarrow 'a'~).

Có 3 loại truy vấn cần thực hiện:

• 1 l r x: Thực hiện thao tác shift các ký tự từ vị trí ~l~ đến ~r~ của xâu ~S~ tổng cộng ~x~ lần.

• 2 l r x: Thực hiện thao tác shift các ký tự từ vị trí ~l~ đến ~r~ của xâu ~T~ tổng cộng ~x~ lần.

• 3 l: So sánh hai hậu tố ~S[l \dots n]~ và ~T[l \dots n]~. In ra ~<~ nếu xâu ~S~ bé hơn, ~>~ nếu xâu ~S~ lớn hơn, hoặc ~=~ nếu hai xâu bằng nhau (theo thứ tự từ điển).

Input

Dòng đầu tiên gồm ba số nguyên dương ~n~, ~c~ và ~q~ ~(1 \le n, q \le 2 \times 10^5, 2 \le c \le 26)~.

Dòng thứ hai chứa xâu ~S~, dòng thứ ba chứa xâu ~T~. Cả hai xâu đều có độ dài ~n~ và chỉ chứa ~c~ ký tự đầu tiên của bảng chữ cái tiếng Anh.

~q~ dòng tiếp theo, mỗi dòng chứa một truy vấn theo định dạng đã mô tả. Trong các truy vấn loại 1 và 2, ~1 \le l \le r \le n~ và ~1 \le x < c~. Với truy vấn loại 3, ~1 \le l \le n~.

Output

Với mỗi truy vấn loại 3, in ra kết quả tương ứng (~<~, ~>~, hoặc ~=~) trên một dòng.

Scoring

Sample Input 1

3 4 3
abc
abd
3 1
1 3 3 1
3 1

Sample Output 1

<
=