{"code":"vostr","name":"Xử lý xâu","description":"Bờm là một học sinh chuyên tin. Hôm nay Bờm được thầy dạy về thứ tự từ điển và các bài toán liên quan. Sau một hồi giảng giải và định nghĩa thứ tự từ điển là gì, thầy lấy ngay một ví dụ cho lớp. Thầy viết lên bảng 2 chuỗi kí tự dài ơi là dài, và hỏi cả lớp \"Chuỗi thứ nhất có thứ tự từ điển như thế nào đối với chuỗi thứ hai: đứng trước (`<`), đứng sau (`>`) hay bằng nhau (`=`) ???\".\r\n\r\nCả lớp thì đang hoang mang, vì cũng chẳng có ai hiểu được định nghĩa \"Thứ tự từ điển là gì?\" của thầy, nói gì đến việc giải bài tập. Nhưng Bờm thì ngược lại, do đã chuẩn bị và xem bài trước ở nhà nên đã trả lời ngay được câu hỏi của thầy sau khi thấy vừa dứt lời. Bờm ngồi chơi trong lúc mọi người đang thảo luận xôn xao, nên đã tạo thêm một số ví dụ nữa về thứ tự từ điển để có thể hiểu sâu thêm về bài học. Nhìn ngay lên bảng, Bờm phát hiện từ 2 xâu trong ví dụ của thầy, Bờm có thể tự sinh ra rất nhiều ví dụ khác. Cụ thể hơn, Bờm chọn một xâu con trong xâu thứ nhất và một xâu con trong xâu thứ hai, thế là có ngay một cặp xâu để mà so sánh. Xâu con ở đây được hiểu là một dãy các ký tự liên tiếp.\r\n\r\nThế là Bờm liên tục sinh ra các ví dụ và trả lời chúng. Bờm càng làm càng nhạy, và trả lời các câu hỏi về thứ tự từ điển càng nhanh. Đến nỗi trong 1 giây Bờm đã có thể trả lời đến tất cả là $10^6$ câu hỏi!\r\n\r\n**Yêu cầu**: Cho 2 xâu kí tự $A$ và $B$ (chỉ gồm các kí tự từ `a` đến `z`) và một danh sách gồm $Q$ câu hỏi có dạng ($l, r, u, v$), với ý nghĩa cần so sánh thứ tự từ điển của xâu con $A[l…r]$ và $B[u…v]$ (các kí tự của một xâu được đánh số từ trái qua phải, bắt đầu bằng 1; và ký hiệu $A[l…r]$ thể hiện xâu con từ kí tự thứ $l$ đến $r$ của xâu A).\r\nBạn hãy viết một chương trình mô tả lại hoạt động trả lời các câu hỏi của Bờm.\r\n\r\n***Lưu ý***\r\nXâu $a_1a_2…a_n$ ($a+i$ là kí tự thứ $i$ trong xâu $a$) có thứ tự từ điển nhỏ hơn xâu $b_1b_2…b_m$ nếu:\r\n- $nInput\r\n\r\n- Dòng đầu tiên gồm 2 số nguyên dương $L_A, L_B$ là độ dài của xâu $A$ và xâu $B$.\r\n- Dòng thứ hai là xâu $A$.\r\n- Dòng thứ ba là xâu $B$.\r\n- Dòng tư là số nguyên dương $Q$ - số câu hỏi trong danh sách\r\n- $Q$ dòng tiếp theo, mỗi dòng gồm 4 số nguyên dương $l, r\\ (1\\le l\\le r\\le L_A), u, v\\ (1\\le u\\le v\\le L_B)$ mô tả một câu hỏi cần trả lời.\r\n\r\n

Output

\r\n\r\n- Với mỗi truy vấn, in ra 1 ký tự `=`, `>` hoặc `<`. Tất cả các câu trả lời được viết trên một dòng.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ ($40\\%$ số điểm): $|A|, |B|, Q\\le 10^3$.\r\n- Subtask $2$ ($60\\%$ số điểm): $|A|, |B|, Q\\le 10^6$.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 13 14\r\n bomthichdacau\r\n bomthichdabanh\r\n 3\r\n 1 10 1 10\r\n 1 10 1 11\r\n 1 11 1 11\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n =<>\r\n ```","points":300.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}