AIOC Banner

Problem: Flowers

Want to try solving this problem? You can submit your code online if you log in or register.


Flowers

Input File: flowin.txt
Output File: flowout.txt
Time Limit: 0.2 second

You run a florist in central Oklahoma where the land is bare and nothing grows. In an effort to boost your sagging sales, you decide to experiment with different types of fertiliser.

You take a square patch of land and divide it into four quarters. The quarters are numbered from 1 to 4 as shown below. In each quarter you use a different type of fertiliser, and throughout the spring you record where the flowers grow.

 1  2 
 3  4 

At the end of spring you have a long list of coordinates, each pair of coordinates representing a flower that appeared. Your task is to determine which fertiliser produced the most flowers.

Input

The first line of the input file will contain the single integer N representing the size of each quadrant (1 <= N <= 1,000). The second line will contain the single integer M representing the total number of flowers whose coordinates you recorded (1 <= M <= 100,000).

Following this will be M lines, each representing a single flower. Each of these lines will be of the form x y, where x and y are the integer x- and y-coordinates at which the flower grew (1 <= x,y <= 2N).

The diagram below shows how the coordinates are located on the patch of land. Quarters 1 and 3 have x coordinates from 1 to N inclusive; quarters 2 and 4 have x coordinates from N+1 to 2N inclusive. Quarters 1 and 2 have y coordinates from 1 to N inclusive; quarters 3 and 4 have y coordinates from N+1 to 2N inclusive.

Note that over the course of spring, many different flowers might appear at the same location.

Output

The output must be a single line of the form q f, where q is the quarter that produced the most flowers and f is the number of flowers that this quarter produced. You may assume that there is always a single quarter with the most flowers.

Sample Input

3
7
2 2
6 2
2 5
2 3
6 5
1 3
5 6

Sample Output

1 3

The scenario above represents the following plot of land. In this case the best quarter is quarter 1 which produced 3 flowers.

Scoring

The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 24 May 2019, 11:54pm AEST