Cuộc chiến tranh chống đế quốc Mĩ là một trong những cuộc chiến tranh tàn khốc và đẫm máu nhất trong lịch sử của Vê Be(Wb). Mặc dù bây giờ hòa bình đã trở lại, nhưng những vết tích của chiến tranh vẫn hằng sâu trong tâm trí của mỗi người lính.

BeTapDi - Tổng tham mưu trưởng quân đội nhân dân Vê Be(Wb) đã bày tỏ những cảm xúc kinh hoàng khi nhớ lại cuộc chiến tranh khốc liệt này. Ông nói: "Hồi đó, lúc còn đánh ở Đà Nẵng, ngày nào tui cũng nghe tiếng máy bay với bom nổ rầm trời, mấy thằng Mĩ nó lái \(R52\) thả bom như mưa, tôi ở dưới hầm mà sợ còn hơn trên mặt trận vì không biết khi nào mình đi thỉnh kinh. Mấy đứa bạn tôi thấy quá sợ khi phải trải qua những ngày như thế nên bọn nó làm liều, xông ra mặt trận quyết tử nên quyên sinh luôn. Còn mỗi tôi với ông đại úy, 2 người chả biết làm gì đành trốn dưới hầm mấy ngày liền. Tự dưng bọn Mĩ nó không thả bom nữa, cũng chả thấy tên lính hay chiếc \(R52\) nào nên bọn tôi bèn đi lên thì thấy cái cảnh hoang tàn hệt như lúc tôi nấu ăn ở nhà vậy. À mà thực ra mấy chiếc đó là \(B52\), nhưng vì bom nó nổ ra cái \(hình\) \(thoi(rhombus)\) nên tui đặt là \(R52\) luôn cho nó dễ hiểu."

Ông nói thêm: "Thấy cái cảnh đó lòng tôi đau như cắt. Ông đại úy cũng vậy, nhìn mà thấy bủh bủh, lmao. Ông ấy lệnh cho tôi đi đo lường thiệt hại của Đà Nẵng (Measure of Damage). Sau khi nghe ông đại úy nói Đà Nẵng diện tích khổng lồ tận \(N * M\) thì tui cũng choáng luôn. Hên là trước khi đi lính, tui có học 1 khóa C++ với lại ở đó cũng có cái laptop khá xịn nên tui nhảy vô code luôn cái chương trình đo lường. Mà tui lại mắc phải cái vấn đề là không có số liệu, chỉ thấy cái cảnh hoang tàn đó thì làm sao đo được. Thế là tui hỏi ông đại úy, ổng nói là lúc trong hầm chán quá, ổng nghe tiếng bom nổ rồi ghi lại nơi tất cả quả bom rơi và độ lớn của vụ nổ nhờ tiếng nổ. Với độ lớn vụ nổ là \(power\) và vụ nổ xảy ra tại ô \((x, y)\) thì những ô có khoảng cách Manhattan tới ô \((x, y) <= power\) sẽ bị ảnh hưởng. Tui thề lúc đó tui cũng không hiểu ổng có phải thần hay là tiên nữa mà nói chung là ảo diệu thật sự. Nhưng mà có nhiều chỗ bom rơi nhiều quá nên ông đại úy muốn đo lường thiệt hại ở nơi đó vào thời điểm đó nên cuối cùng cái danh sách của ổng cũng loạn luôn. Giờ tui vẫn còn giữ cái danh sách ở đây nên tui muốn xem thử các bạn đang đọc cái đề này giải thử xem trình học sinh ngày nay thế nào =))"

Input

Dòng đầu tiên chứa bốn số \(Task,\) \(N,\) \(M,\) \(Q\) lần lượt là số thứ tự subtask, chiều rộng, chiều dài của Đà Nẵng và số lượng truy vấn của danh sách.

\((1 \le Task \le 3),\) \((1 \le N, M \le 10^9),\) \((1 \le Q \le 10^5)\).

\(Q\) dòng tiếp theo, dòng thứ \(i\) chứa \(t[i]\) \((1 \le t[i] \le 2)\) là loại truy vấn của truy vấn thứ \(i\).

• Với \(t[i] = 1\), dòng đó sẽ chứa thêm 3 số \(x[i],\) \(y[i]\) và \(pow[i]\) lần lượt là vị trí xảy ra vụ nổ và độ lớn vụ nổ.
• Với \(t[i] = 2\), dòng đó sẽ chứa thêm 2 số \(x[i],\) \(y[i]\) tức là BeTapDi muốn bạn trả lời xem rằng ô \((x[i], y[i])\) đã bị ảnh hưởng bởi bao nhiêu vụ nổ.

\((1 \le x[i] \le N),\) \((1 \le y[i] \le M),\) \((1 \le pow[i] \le max(N, M))\)

Output

Với mỗi truy vấn loại 2, in ra một số trên một dòng là số vụ nổ đã ảnh hướng tới ô ở truy vấn đấy.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \((1 \le N, M \le 200),\) \((1 \le Q \le 100)\)
• Subtask \(2\) (\(30\%\) số điểm): \((1 \le N, M \le 1000),\) \((1 \le Q \le 1000)\)
• Subtask \(3\) (\(40\%\) số điểm): \((1 \le N, M \le 10^9),\) \((1 \le Q \le 10^5)\)

Example

1 8 11 6
1 5 8 3
2 5 11
1 3 11 2
2 3 9
1 5 11 0
2 5 11

1
2
3