Hôm nay cô giáo Ngattaro vừa dạy cho Necrophos bảng chữ cái tiếng Anh. Để nhớ được hoàn toàn 26 ký tự trong bảng chữ cái, cậu đã viết liên tục 26 chữ cái theo thứ tự từ ~a~ tới ~z~ ra vở để nhớ được tốt hơn.

Quá trình này thực ra cực kỳ buồn chán, nên Necrophos đã nghĩ ra một cách để làm việc học thuộc trở nên thú vị hơn: Thay vì viết các chữ cái đơn lần lượt theo từng hàng, cậu sẽ viết dãy chữ cái vào một bảng vuông:

• Bảng hình vuông có kích thước ~n~ x ~n~ với chỉ số hàng được đánh số từ ~1~ tới ~n~ (trên xuống dưới) và chỉ số cột được đánh số từ ~1~ tới ~n~ (trái sang phải).
• Necrophos sẽ luôn bắt đầu điền bảng vuông từ chữ cái ~a~ vào ô ~[1,1]~, sau đó viết tiếp theo thứ tự hình xoắn ốc thuận chiều kim đồng hồ cho đến khi kín cả bảng.
• Viết lần lượt theo thứ tự từ điển từ ~a~ đến ~z~, sau đó viết các cặp chữ cái từ ~aa~ tới ~zz~, rồi ~aaa~ cho đến ~zzz~ ...

Ví dụ với bảng có kích thước ~n = 6~:

Không dừng lại ở đây, để cố gắng thử thách khả năng ghi nhớ và tính toán của mình, Necrophos muốn thử đoán xem với một bảng có kích cỡ ~n~ x ~n~ cho trước thì chuỗi ký tự ~s~ sẽ xuất hiện tại vị trí nào trong bảng vuông.

Yêu cầu

Cho kích thước của bảng vuông ~n~ và ~q~ truy vấn, mỗi truy vấn chứa một chuỗi ký tự ~s~. Với mỗi truy vấn, hãy tính ra vị trí hàng và cột chứa chuỗi ký tự ~s~.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n~, ~q~ ~(1≤n≤10^7, 1≤q≤10^6)~ cách nhau một dấu cách.
• ~q~ dòng sau, mỗi dòng chứa một chuỗi ký tự ~s~ chỉ bao gồm các chữ cái thường.

Output

• ~q~ dòng, mỗi dòng chứa hai số nguyên là vị trí hàng và cột của ô chứa chuỗi ký tự của từng truy vấn, giữa hai số cách nhau một dấu cách.

Lưu ý: Dữ liệu đảm bảo chuỗi ký tự có xuất hiện trong bảng vuông.

Sample Input

6 3
g
v
ah

Sample Output

2 6
2 3
3 4

Subtask

• Có 30% số test ứng với 30% số điểm có ~1≤n≤10^3~;
• Có 30% số test ứng với 30% số điểm có ~1≤n≤10^6, q=1~;
• Có 20% số test ứng với 20% số điểm có ~1≤n≤10^6, 1≤q≤10^5~;
• 20% số test còn lại tương ứng với 20% số điểm không có giới hạn gì thêm.