Thời buổi khoa học công nghệ, biết mình không thể nhờ cậy tài phép của thần đèn mãi được nên Aladdin quyết tâm trau dồi kiến thức tin học. Aladdin đặc biệt thích lập trình. Dưới sự kèm cặp của Abu và thần đèn, Aladdin tập luyện ngày đêm nuôi ước mơ đại diện xứ Ba Tư tham dự kì thi IOI.

Trong một lần làm bài, Aladdin phải nhập dữ liệu vào một bảng ~A~ kích thước ~M\times N~ ~(M~ hàng, ~N~ cột). Tuy nhiên, do đang mải mơ màng nghĩ tới Jasmine nên Aladdin lại nhập thành bảng ~N\times M~ và giá trị đáng ra phải ghi vào bảng ~A~ ở hàng ~i~ cột ~j~ thì ~H~ lại ghi vào hàng ~j~ cột ~i~. Ví dụ với ~M = 3~, ~N = 4~:

Bảng Aladdin phải nhập: $$\begin{array}{|l|l|l|l|} \hline 3 & 4 & -10 & 5 \\ \hline 6 & 7 & 0 & -12 \\ \hline 2 & 1 & 9 & 20 \\ \hline \end{array}$$

Bảng Aladdin nhập vào: $$\begin{array}{|l|l|l|} \hline 3 & 6 & 2 \\ \hline 4 & 7 & 1 \\ \hline -10 & 0 & 9 \\ \hline 5 & -12 & 20 \\ \hline \end{array}$$

Aladdin định nhập lại từ đầu, nhưng tá hỏa khi biết file dữ liệu đầu vào đã bị virus ăn mất. Vậy nên Aladdin phải viết một chương trình để đưa dữ liệu về bảng ~A~ về đúng yêu cầu. Kẹt nỗi mọi chuyện không đơn giản vì Aladdin dùng một máy vi tính đặc biệt. Máy này lưu bảng ~A~ dưới dạng một mảng một chiều kích thước ~M\times N~ và sẽ ghi lần lượt lên mảng này theo thứ tự nhập (theo từng dòng, trên mỗi dòng theo từng cột).

VD: nếu Aladdin nhập đúng thì mảng ~A~ sẽ như sau: $$\begin{array}{|l|l|l|l|l|l|l|l|l|l|l|l|} \hline 3 & 4 & -10 & 5 & 6 & 7 & 0 & -12 & 2 & 1 & 9 & 20 \\\\ \hline \end{array}$$

Máy của Aladdin có ~2~ chế độ: ở chế độ ~1~ có thể đổi vị trí ~2~ phần tử bất kì ở vị trí ~i~ và ~j~, còn ở chế độ ~2~ nó chỉ có thể đổi vị trí ~2~ phần tử liên tiếp ~i~ và ~i~ + ~1~

Aladdin định viết ~1~ chương trình để đưa mảng ~A~ về trạng thái đúng. Tuy nhiên trước khi bắt tay vào code, Aladdin muốn biết sẽ tốn ít nhất bao nhiêu phép hoán đổi để đưa bảng về dữ liệu đúng. Có một điều may mắn là Aladdin nhớ rằng khi nhập dữ liệu vào không có ~2~ phần tử nào có giá trị bằng nhau. Có thể điều này sẽ giúp việc tính toán dễ dàng hơn.

Input

• Dòng đầu tiên gồm ~3~ số nguyên dương ~M~, ~N~ là kích thước đúng của bảng ~A~
• Dòng tiếp hai gồm ~1~ số duy nhất ~S~ là chế độ hiện thời của máy ~(1~ hoặc ~2)~.

Output

• Ghi ra một số nguyên duy nhất là số phép hoán đổi ít nhất cần thực hiện để đưa bảng về đúng trạng thái.

Giới hạn

• ~1 \leq M~, ~N \leq~ ~5\times 10^5~
• ~M\times N~ ~\leq~ ~5\times 10^5~
• Trong ~30\%~ số test với ~S = 2~, ~M\times N~ ~\leq 5000~

Sample Input 1

2 4
1

Sample Output 1

4

Sample Input 2

2 4
2

Sample Output 2

6

Note

• Trong khi thi submission sẽ được chấm ~2~ test, ~1~ test ~S = 1~ và ~1~ test ~S = 2~