heap

Plus

Problem description Progress

ID 30754. Finding the Minimum Using Priority Queue

Темы: heap

Given a sequence of numbers. Find the smallest number in it.

Input

The number N is given first (the number of numbers in the sequence, 1<=N< ;=100000) and then

N numbers.

Output

Print the smallest number.

Enter	Output
7 4 2 5 -1 4 6 2	-1

ID 30723. Pyramid (maximum)

Темы: heap

Write a program that will process a sequence of queries like this:

CLEAR — make the pyramid empty (if there were already some elements in the pyramid, delete all). The action occurs only with the data in memory, nothing is displayed on the screen.

ADD n — add the number n to the pyramid. The action occurs only with the data in memory, nothing is displayed on the screen.

EXTRACT — take out the maximum value from the pyramid. You should both change the data in memory and display either the maximum value found, or, if the pyramid was empty, the word "CANNOT" (in capital letters).

Input

The input contains an arbitrary sequence of queries CLEAR, ADD and EXTRACT — each on a separate line, following the format described above. The data ends with the string "END!"

The total number of all requests does not exceed 200000.

Output

For each EXTRACT query, print its result to the standard output (screen) (on a separate line).

Enter	Output
ADD 192168812 ADD 125 ADD 321 EXTRACT EXTRACT CLEAR ADD7 ADD 555 EXTRACT EXTRACT EXTRACT END!	192168812 321 555 7 CANNOT

ID 33256. Cat Goose and random matrix

Темы: heap Prefix sums(minimums, ...)

Cat Goose prepared for Nick Fury a rectangular table a of size \(n \cdot m\) containing numbers from 0 code> to p−1. Nick Fury immediately realized that each number in this table was chosen randomly with equal probability from 0 to p−1 , regardless of the others.



Your task — find a rectangular submatrix of this table, in which the sum is divisible by p. Among all such submatrices, you need to find the one in which the sum of the elements is maximum.
Formally, you need to find \(1 <= i_1 <= i_2 <= n\), \( 1 <= j_1 <= j_2 <= m\) that the sum of a_x,y over all \(i_1 <= x <= i_2\), \(j_1 <= y <= j_2\) split on p, and among these has the maximum amount.





Input

The first line contains three integers n, m, p (\(1 <= n m, p <= 1,000,000\)) — dimensions of the matrix and the number by which the sum of the submatrix should be divided.

The following n lines contain m integers, the j-th number in the i-th line equals a_i,j (\(0 <= a_{i,j} <= p ? 1\) ).

It is guaranteed that each number in a is chosen independently at random, equiprobably from 0 to p−1.



Output

Print a single integer — the maximum sum of a rectangular submatrix where the sum is divisible by p. If there are none, print 0.

 

Examples




#
Input
Output




1

6 7 5

0 0 3 0 1 0 4

0 2 3 0 2 2 1

2 4 1 4 4 0 3

1 1 0 2 0 3 2

3 0 3 1 0 1 2

1 2 0 0 3 3 1

65