Một hội chợ được tổ chức trên một quảng trường hình chữ nhật. Quảng trường được chia thành lưới ô vuông kích thước \(w \times h\). Các hàng được đánh số từ \(1\) đến \(w\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(h\) từ trái sang phải, ô nằm giao giữa hàng \(i\), cột \(j\) được gọi là ô \((i,j)\). Ban tổ chức muốn làm hai đường đi bộ trên đó, một đường sẽ được làm song song với chiều dọc của quảng trường, đường còn lại được làm song song với chiều ngang của quảng trường. Để hai con đường được xây dựng một cách thẩm mĩ, người ta muốn chiều rộng của hai con đường phải bằng nhau. Có \(n\) ô vuông được đặc biệt, Ban tổ chức muốn hai đường đi bộ này cần phải phủ hết \(n\) ô vuông này. Tuy nhiên, kinh phí để trang trí hai con đường này không nhiều, do đó người ta muốn làm hai con đường này có chiều rộng nhỏ nhất có thể.

Yêu cầu: Hãy tìm chiều rộng nhỏ nhất của hai con đường như mô tả trên.

Input

• Dòng đầu tiên chứa ba số nguyên \(w,h,n\) (\(n \le min(w \times h, 3 \times 10^5)\)).
• \(n\) dòng tiếp theo mỗi dòng chứa hai số \(x,y\) (\(1 \le x \le w, 1 \le y \le h\)) mô tả vị trí đặc biệt.

Output

• Một số nguyên là chiều rộng nhỏ nhất có thể của hai con đường.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(w,h,n \le 500\).
• Subtask \(2\) (\(25\%\) số điểm): \(w,h \le 10^9, n \le 2000\).
• Subtask \(3\) (\(25\%\) số điểm): \(w,h \le 2000\).
• Subtask \(4\) (\(25\%\) số điểm): \(w,h \le 3 \times 10^5\).
• Subtask \(5\) (\(10\%\) số điểm): \(w,h \le 10^9\).

Example

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

3

Minh mới tạo ra một robot có khả năng nhận dạng trên sàn và di chuyển theo các chỉ dẫn đó. Sàn là một bảng gồm \(R\) hàng và \(C\) cột. Các hàng được đánh số từ \(1\) đến \(R\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(C\) từ trái sang phải. Ô ở hàng thứ \(u\) (\(1 \le u \le R\)) và cột thứ \(v\) (\(1 \le v \le C\)) được gọi là ô \((u,v)\). Mỗi ô của bảng sẽ có chỉ dẫn cho bước đi tiếp theo của robot.

Ví dụ, bảng dưới là một ví dụ:

• Robot ban đầu ở vị trí \((1,1)\), bước tiếp theo robot sẽ di chuyển sang phải tới ô \((1,2)\).
• Ở ô \((1,2)\), robot nhận chỉ dẫn di chuyển tiếp xuống dưới là ô \((2,2)\).
• Ở ô \((2,2)\), robot nhận chỉ dẫn di chuyển tiếp xuống dưới là ô \((3,2)\).
• Ở ô \((3,2)\), robot nhận chỉ dẫn di chuyển lên trên là ô \((2,2)\).
• Robot sẽ di chuyển giữa hai ô \((2,2)\) và \((3,2)\).

Minh muốn thử nghiệm đưa robot di chuyển từ ô \((x_s,y_s)\) tới được ô \((x_t,y_t)\) nhưng bảng hướng dẫn có thể không làm cho robot di chuyển được như vậy. Bạn được quyền thay đổi hướng dẫn của một số ô để robot có thể đi từ \((x_s,y_s)\) đến \((x_t,y_t)\). Nhiệm vụ của bạn là chọn ít nhất các ô và thay đổi chỉ dẫn của các ô này để robot có thể đi từ \((x_s,y_s)\) đến \((x_t,y_t)\). Nếu có nhiều cách thay đổi chỉ dẫn các ô, hãy đếm số cách thay đổi khác nhau. Trường hợp không cần thay đổi ô nào thì số cách là \(1\). Ngược lại, hai cách thay đổi được coi là khác nhau nếu một trong hai điều sau xảy ra:

• Tồn tại một ô được thay đổi trong cách thứ nhất mà không được thay đổi trong cách thứ hai.
• Tồn tại một ô dược thay đổi trong cả hai cách, nhưng chỉ dẫn sau khi thay đổi ở cách thứ nhất khác cách thứ hai.

Input

• Dòng đầu chứa ba số \(R,C\) và \(q\), trong đó \(R,C\) là kích thước của bảng và \(q\) là số trường hợp thử nghiệm.
• Tiếp theo là \(R\) dòng, mỗi dòng chứa xâu kí tự độ dài \(C\). Kí tự thứ \(v\) trên dòng thứ \(u\), thể hiện chỉ dẫn của ô \((u,v)\). Chỉ dẫn thuộc một trong bốn kí tự U, D, L, R tương ứng với đi lên trên, xuống dưới, sang trái, sang phải.
• \(q\) dòng cuối, mỗi dòng chứa bốn số nguyên \(x_s,y_s,x_t,y_t\) tương ứng với một thử nghiệm.

Output

• Gồm \(q\) dòng, mỗi dòng gồm hai số cách nhau một dấu cách: số thứ nhất ghi ra số ô phải thay đổi ít nhất, số thứ hai là phần dư trong phép chia số cách thay đổi khác nhau chia cho \((10^9+7)\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(R,C \le 4, q \le 3\).
• Subtask \(2\) (\(15\%\) số điểm): \(R = 1, q \le 3\).
• Subtask \(3\) (\(20\%\) số điểm): \(R,C \le 100, q \le 3\).
• Subtask \(4\) (\(20\%\) số điểm): \(R,C \le 1000, q \le 3\).
• Subtask \(5\) (\(10\%\) số điểm): \(R,C \le 1000, q \le 10\).
• Subtask \(6\) (\(20\%\) số điểm): \(R \times C \le 10^6, q \le 10\).

Example

3 4 2
RDRD
RDRD
UUUL
1 1 3 2
1 1 3 4

0 1
1 3

2 2 1
UD
RR
1 1 2 2

1 2

Có \(n\) khu vực dân cư, khu vực \(i\) ở vị trí \((x_i,y_i)\). Người ta muốn đặt \(k\) siêu thị để cung cấp hàng hóa cho \(n\) khu vực dân cư này. Người dân ở khu vực dân cư \(i\) khi mua hàng sẽ chọn siêu thị gần nhát, do đó tiêu chí đánh giá việc đặt \(k\) siêu thị dựa trên giá trị: tổng khoảng cách của từng khu vực dân cư đến siêu thị gần nhất, giá trị này càng nhỏ càng thể hiện việc chọn là tối ưu.

Yêu cầu: Cho \(n,k\) và tọa độ của \(n\) khu dân cư. Hãy xác định vị trí đặt \(k\) siêu thị để tổng các khoảng cách của từng khu vực dân cư đến siêu thị gần nhất càng nhỏ càng tốt.

Input

• Dòng đầu chứa hai số nguyên \(n,k\) (\(k \le n\)).
• \(n\) dòng sau, mỗi dòng chứa hai số thực \(x_i,y_i\) (\(0 \le x_i,y_i \le 10000\)).

Output

• Gồm \(k\) dòng, mỗi dòng chứa hai số thực là tọa độ của các siêu thị.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 15\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 5000\).
• Cách tính điểm: Với mỗi test, gọi tổng khoảng cách theo phương án của giám khảo là \(res\), gọi tổng khoảng cách theo phương án của thí sinh là \(ans\), điểm số tính theo công thức sau: \(min(1,(\frac{res}{ans}))^2\).

Example

5 2
0 0
1 0
1 1
0 1
9 9

0.5 0.5
9 9