Cho xâu ~S~ gồm các kí tự trong bảng chữ cái từ ~a~ tới ~z~ có độ dài ~n~.

Cho ~q~ truy vấn, mỗi truy vấn có dạng ~(x,y,u,v)~, hỏi hai xâu ~S[x:y]~ và ~S[u:v]~ có bằng nhau không? Biết ~y - x = u - v~.

Input

• Dòng đầu là hai số nguyên dương ~n~ và ~q~ miêu tả độ dài xâu và số truy vấn ~(1 \le n,q \le 2 \times 10^5)~.
• Dòng hai gồm xâu ~S~.
• ~q~ dòng sau, mỗi dòng gồm bốn số nguyên dương ~(x,y,u,v)~ ~(1 \le x \le y \le n; 1 \le u \le v \le n)~ miêu tả truy vấn.

Output

• Với mỗi truy vấn, nếu chúng bằng nhau in ra ~1~, ngược lại in ra ~0~ theo từng dòng.

Sample Input 1

5 3
ababa
1 3 3 5
1 4 2 5
1 1 3 3

Sample Output 1

1
0
1

Một xâu xoay được tạo ra bởi chuyển một chữ cái từ cuối lên đầu xâu. Ví dụ, các xâu xoay của ~marisa~ là ~marisa, amaris, samari, isamar, risama~ và ~arisam~.

Hãy xác định xâu xoay có thứ tự từ điển nhỏ nhất của xâu ~S~ cho trước.

Input

• Gồm một dòng chứa xâu ~s~.

Constraints

• ~1 \le |s| \le 10^6~

Subtask:

• Subtask ~1~ (~50\%~ số điểm): ~n \le 10^3~
• Subtask ~2~ (~50\%~ số điểm): ~n \le 10^6~

Output

• In ra xâu có thứ tự từ điển nhỏ nhất.

Sample Input 1

marisa

Sample Output 1

amaris

Cho xâu ~S~ gồm các kí tự trong bảng chữ cái từ ~a~ tới ~z~ có độ dài ~n~.

Hãy in ra xâu con liên tiếp dài nhất của ~S~ sao cho nó là một palindrome.

Input

• Gồm xâu ~S~. ~|S| \le 10^6~.

  Output

• In ra xâu con liên tiếp dài nhất là palindrome.

Sample Input 1

aybabtu

Sample Output 1

bab

Cho một xâu nhị phân S độ dài ~n~ (các chỉ số được đánh số từ ~1~) và ~q~ truy vấn thuộc một trong hai loại:

• ~1 \; u \; x~: Gán ~S_u = x~, trong đó ~x \in \{0, 1\}~.
• ~2 \; u \; v \;x~: Kiểm tra xem hai xâu ~S[u..u+x-1]~ và ~S[v..v+x-1]~ có bằng nhau không. Nói cách khác, kiểm tra xem hai xâu con liên tiếp độ dài ~x~ bắt đầu từ ~u~ và ~v~ có bằng nhau không?

Với mỗi truy vấn ~2~, hãy in ra ~1~ nếu hai xâu bằng nhau, ~0~ là ngược lại.

Input

• Dòng đầu tiên gồm xâu ~S~ có độ dài ~n~.
• Dòng thứ hai gồm số nguyên ~q~ - số truy vấn.
• ~q~ dòng sau, mỗi dòng là ba hoặc bốn số nguyên dương thuộc một trong hai loại như miêu tả trên.

Constraints

• ~1 \le n, q \le 2 \times 10^5~
• ~1 \le u + x - 1, v + x - 1 \le n~

Subtasks

• Subtask ~1~ ~(30\%)~: ~1 \le n, q \le 3000~.
• Subtask ~2~ ~(70\%)~: Không còn điều kiện gì thêm.

Output

• Gồm một xâu nhị phân gồm ~q~ kí tự ~0~ và ~1~.

Sample Input 1:

1000100
3
2 1 5 3
1 3 1
2 1 3 3

Sample Output 1:

11

Explanation 1:

Truy vấn đầu tiên có ~S[1..3] = 100~, ~S[5..7] = 100~. Truy vấn thứ hai xâu ~S~ trở thành ~1010100~ Truy vấn thứ ba có ~S[1..3] = 101~, ~S[3..5] = 101~.

Gọi ~S(l,r,a)~ là Set của các phần tử từ ~l~ tới ~r~ trong mảng ~a~. Ví dụ, nếu ~a = [1,1,1,3,3,2]~ thì ~S(1,6, a) = [1,2,3]~; ~S(4,6,a) = [2,3]~.

Cho hai mảng các số nguyên dương ~a~ và ~b~ có kích thước là ~n~. Bạn có ~q~ truy vấn, truy vấn thứ ~i~ cho bốn số ~l_i~, ~r_i~ và ~x_i~, ~y_i~. Với mỗi truy vấn, hãy kiểm tra xem ~S(l_i,r_i,a)~ có bằng với ~S(x_i,y_i,b)~ hay không.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ (~1 \leq n, q \leq 2 \cdot 10^5~).

• Dòng tiếp theo chứa ~n~ số nguyên dương là các phần tử mảng ~a~ (~1 \leq a_i \leq 10^9~).

• Dòng tiếp theo chứa ~n~ số nguyên dương là các phần tử mảng ~b~ (~1 \leq b_i \leq 10^9~).

• ~q~ dòng tiếp, dòng thứ ~i~ chứa ~4~ số nguyên dương ~l_i~, ~r_i~ và ~x_i~, ~y_i~ (~1 \leq l_i \leq r_i \leq n~, ~1 \leq x_i \leq y_i \leq n~).

Output

• In ra ~q~ dòng, nếu ~S(l_i,r_i,a)~ bằng với ~S(x_i,y_i,b)~ in ra ~\textbf{YES}~, ngược lại in ra ~\textbf{NO}~.

Scoring

Sample Input 1

6 5
1 1 1 2 3 2
1 2 1 3 2 1
1 6 1 6
3 6 2 5
2 5 4 5
1 4 2 3
1 3 2 4

Sample Output 1

YES
YES
NO
YES
NO