Indian National Olympiad in Informatics

Related:

Online Programming Contest, 2-3 October 2004

IARCS home > OLYMPIAD

Basic Division

Problem 1: BCCS Elections, (K Narayan Kumar, CMI)

The Board of Cricket Control of Siruseri holds an election every year to elect a 3 member executive committee to run the affairs of the board. The executive committee is quite powerful, as it decides which television company gets to broadcast the Siruseri Cricket League and so on. The procedure for this election is the following. All those interested in serving as executive committee members inform the Manager. The Manager informs all the members of the BCCS about the list of candidates. On the day of the election, each member of BCCS is allowed to vote for exactly one of the candidates. Finally all the votes are counted and the top three candidates are deemed elected.

Suppose there are 5 candidates {1,2,3,4,5}, 10 members in all in BCCS and the votes cast are as follows:

Voter  Vote

   1  	2
   2  	5
   3  	4
   4  	4
   5  	3
   6  	1
   7  	2
   8  	1
   9  	1
  10  	2

Then, candidates 1, 2 (with 3 votes each) and 4 (with 2 votes) are elected to the executive committee.

You are given the number of candidates and voters and the list of votes. Your task to determine the candidate finishing third. You may assume that the votes are cast in such a way that there is never a tie between the second and third best candidates or between the third and fourth best candidates.

Input format

The first line of the input consists of two integers C and N, where C is the number of candidates and N is the number of voters. The next N lines, lines 2,..., N+1, provide information on the votes. Line i+1, 1 ≤ i ≤ N, contains a single integer Vi, 1 ≤ Vi ≤ C, indicating the choice of voter i.

Output format

The output must consist of a single line with a single integer, indicating the identity of the candidate finishing third.

Test data

You may assume that 3 ≤ N ≤ 100000 and 3 ≤ C ≤ 10000.

Example

We now illustrate the input and output formats using the example described above.

Sample input:

Sample output:

Test data:

10 zipped test inputs and outputs