Hoàng là một cư dân sinh sống tại siêu đô thị Minhomes Sea Playground. Trên bản thiết kế, siêu đô thị này có hình dạng một hình chữ nhật kích cỡ ~M \times N~, được chia thành các lô đất hình vuông kích cỡ ~1 \times 1~ song song với trục tọa độ, lô đất thứ ~i~ từ trên xuống và thứ ~j~ từ trái sang phải được ký hiệu là lô đất ~(i, j)~. Hai lô đất được gọi là liền kề nếu có chung một đường biên. Trên mỗi lô đất có thể được xây dựng duy nhất một biệt thự. Hai biệt thự được gọi là liền kề nếu chúng nằm trên hai lô đất liền kề. Để thuận tiện đi lại giữa các biệt thự, người ta xây dựng một lối đi tắt hai chiều giữa mỗi cặp biệt thự liền kề.

Theo thiết kế, siêu đô thị đã được quy hoạch ~K~ dãy biệt thự liền kề. Một dãy biệt thự chỉ gồm các biệt thự liền kề và tâm lô đất của tất cả các biệt thự trong dãy đều nằm trên một đường thẳng. Nói cách khác, có thể ký hiệu một dãy biệt thự bằng bốn số ~x_1, y_1, x_2, y_2~, có nghĩa là biệt thự nằm ở vị trí trên cùng bên trái của dãy nằm ở lô đất ~(x_1, y_1)~, biệt thự nằm ở vị trí dưới cùng bên phải của dãy nằm ở lô đất ~(x_2, y_2)~ và ~x_1 = x_2~ hoặc ~y_1 = y_2~.

Vì là người rất mê tín, Hoàng rất muốn biết được các tính chất rất đặc thù về siêu đô thị mình sinh sống. Cụ thể, Hoàng rất muốn biết nếu chỉ xét các lô đất nằm trong một số hàng đầu tiên của siêu đô thị thì có bao nhiêu biệt thự và có bao nhiêu thành phần liên thông chỉ gồm các biệt thự biết rằng hai biệt thự được coi là cùng thành phần liên thông nếu có thể di chuyển giữa chúng bằng các lối đi tắt.

Yêu cầu: Với mỗi hàng ~i~ từ ~1~ đến ~M~, hãy tính số lượng biệt thự và số lượng thành phần liên thông nếu chỉ xét các lô đất từ hàng ~1~ tới hàng ~i~.

Input

• Dòng đầu tiên là ba số nguyên dương ~M, N, K~ (~1 \le M, N, K \le 10^5~);
• ~K~ dòng tiếp theo, dòng thứ ~i~ là bốn số nguyên dương ~X_1, Y_1, X_2, Y_2~ (~1 \le X_1 \le X_2 \le M~; ~1 \le Y_1 \le Y_2 \le N~; ~X_1 = X_2~ hoặc ~Y_1 = Y_2~);
• Dữ liệu đảm bảo mỗi căn biệt thự chỉ thuộc về duy nhất một dãy biệt thự.

Output

• In ra ~M~ dòng, dòng thứ ~i~ chứa hai số là số lượng biệt thự và số lượng thành phần liên thông gồm các biệt thự nếu chỉ xét các lô đất từ hàng ~1~ tới hàng ~i~.

Sample Input 1

4 3 4
1 1 1 2
3 1 3 2
1 3 2 3
4 1 4 3

Sample Output 1

3 1
4 1
6 2
9 2