Hai từ X và Y được gọi là tương đương khi sắp xếp thứ tự của các kí tự trong từ X ta thu được từ Y. Ví dụ hai từ abba và aabb là tương đương, nhưng abba không tương đương với aaba.

Yêu cầu: Cho xâu S chỉ gồm n chữ cái in thường (trong bảng chữ cái tiếng Anh), các chữ cái được đánh chỉ số từ 1 đến n theo thứ tự từ trái sang phải. Kiểm tra hai xâu con của S có phải là hai từ tương đương không. Biết rằng: Xâu thứ nhất bắt đầu từ vị trí a đến b, xâu thứ hai bắt đầu từ c đến d ~(1≤a≤b≤n,1≤c≤d≤n)~. . Dữ liệu vaò có cấu trúc như sau:

• Dòng đầu ghi xâu S;
• Dòng thứ hai ghi số nguyên dương T là số lượng các cặp xâu con cần kiểm tra;
• T dòng tiếp theo, mỗi dòng ghi thông tin của 2 xâu con cần kiểm tra gồm 4 số a,b,c,d cách nhau một dấu.

Kết quả. gồm T dòng ghi lần lượt kết quả tương ứng của các cặp xâu được kiểm tra, nếu hai từ tương đương ghi 1, ngược lại ghi 0.

Ví dụ:

input

papamama 
2 
2 2 8 8 
1 4 5 8

Output

1
0

Ràng buộc:

• Có 30% test có n,T≤255 tương ứng 30% số điểm;
• Có 30% test có n,T≤1.000 tương ứng 30% số điểm;
• Có 40% test có n,T≤50.000 tương ứng 40% số điểm.