Our friend Lord Tachanka is on an important mission. He has to reach basecamp quickly. But the evil enemies have stolen many LMG's and have placed them along the way. You'll have to help him out!

Lord Tachanka is initially at the top left corner (1,1) of a rectangular N × M grid. He needs to reach the bottom right corner (N,M). He can only move down or right. He moves at the speed of 1 cell per second. He has to move every second—that is, he cannot stop and wait at any cell.

There are K special cells that contain the LMG planted by the enemies. Each LMG has a starting time t and a frequency f. It first fires at time t seconds, followed by another round at time t+f seconds, then at time t+2f seconds …. When a LMG fires, it simultaneously emits four bullets, one in each of the four directions: up, down, left and right. The pulses travel at 1 cell per second.

Suppose a LMG is located at (x,y) with starting time t and frequency f. At time t seconds, it shoots its first set of bullets. The bullets travelling upwards will be at the cell (x,y-s) at time t+s seconds. At this time, the bullets travelling left will be at cell (x-s,y), the bullets travelling right will be at cell (x+s,y) and the bullets travelling down will be at cell (x,y+s). It will fire next at time t+f seconds. If a bullets crosses an edge of the grid, it disappears. The LMG's are numbered 1 to k, and if two bullets from different LMG's happen to meet, the one coming from the higher numbered LMG survives. At any time, if Lord Tachanka and a bullet are in the same cell, he dies. That is the only way bullet interact with Lord Tachanka. 

But don't be worried, as you can help the Lord. He can contact his basecamp and can report them the exact position of an LMG, and it will be destroyed by air support. But the war is going on, and you as a commander will have to ensure that minimum missiles are wasted.

Given these, you should find the least time (in seconds) in which Lord Tachanka can reach his basecamp safely. Also calculate the minimum LMG's that are needed to be destroyed so that the Lord can reach the basecamp safely.

Constraints

2 <= N, M <= 500

1 <= K <=500

All the frequencies are guaranteed to be integers between 1 and 600, inclusive.

All the starting times are guaranteed to be integers between 0 and 600, inclusive

All the coordinates of the LMGs are guaranteed to be valid cells in the N×M grid.

No two LMGs will be on the same cell.

Input

Line 1: Three space separated integers N, M and K, describing the number of rows and columns in the grid and the number of LMG's, respectively.

Lines 2 to K+1: These lines describe the K LMGs. Each line has four space separated integers. 

The first two integers on the line denote the row and column where the LMG is located, 

the third integer is its starting time, and the fourth integer is its frequency.

The LMG's are numbered in the order in which it appears in the input, i.e. from 1 to k

Output

You need to output two integers, the minimum amount of time required for the Lord to reach the basecamp, and the minimum LMG's needed to be destroyed.

Example

Input:
4 4 1
3 2 1 3
Output:
6 0