Cho ma trận ~n~ x ~n~, các hàng được đánh số từ dưới lên trên, các cột được đánh số từ trái sang phải. Ban đầu người chơi đứng ở ô ~[1, 1]~, hàng ~1~ cột ~1~ (trái dưới), trên ô này được ghi số ~1~. Mỗi bước, người chơi sẽ di chuyển xoắn ốc, thuận chiều kim đồng hồ vào trong (từ ô ~[1, 1]~ đi lên trên, rồi rẽ phải, . . .), đi đến ô nào thì ô đó sẽ được ghi các số lần lượt ~2~, ~3~, ~4~, … ~n~ x ~n~.

Cho ~q~ truy vấn gồm 2 loại:

• ~1~ ~m~: Tìm toạ đô ô mà người chơi đang đứng sau khi di chuyển đến ô được đánh số ~m~.
• ~2~ ~x~ ~y~: Tìm giá trị tại ô có toạ độ ~[x, y]~.

Yêu cầu

Cho ma trận có kích cớ ~n~ x ~n~ và ~q~ truy vấn. Tìm ra đáp án tương ứng với từng loại truy vấn.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n~, ~q~ ~(n≤10^9, q≤10^6)~ cách nhau một dấu cách.
• ~q~ dòng tiếp theo, mỗi dòng là một truy vấn có dạng ~1~ hoặc ~2~.

Output

Gồm ~q~ dòng duy nhất, mỗi dòng chứa kết quả của 1 truy vấn.

Sample Input

5 2
1 10
2 2 2

Sample Output

4 5
17

Subtask

• Có 20% số test ứng với 20% số điểm có ~n≤1000~;
• Có 20% số test ứng với 20% số điểm chỉ chứa các truy vấn loại ~1~ và ~q≤10^5~;
• Có 20% số test ứng với 20% số điểm chỉ chứa các truy vấn loại ~2~ và ~q≤10^5~;
• Có 20% số test ứng với 20% số điểm có ~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.