Description

Please implement a binary min heap that supports the following operations:

- `1 x`: Insert number x
- `2`: Remove an element with largest value in the heap.  If the heap is already empty, ignore this command.
- `3`: Report the largest number in the heap.  If the heap is already empty, print "EMPTY" (without quotation mark).

Input

The first line contains an integer q, being the number of operations.

The following q lines are the operations described in the problem statements.

Restrictions

- 1 <= q <= 2 * 10⁶
- -10⁹ <= x <= 10⁹

Output

For each query with type 3, print the answer in one line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a universe beyond our own, known as the Hamburger Universe, there are N hamburger shop. The coordinates of the i-th hamburger shop are (x_i, y_i). 

The residents of the Hamburger Universe have a fondness for hamburgers. To facilitate a hamburgers exchange conference, they have decided to set up hamburger teleportation gates between the hamburger shops. Specifically, there is a cost of |x_i - x_j| * |y_i - y_j| to set up a gate between the i-th and j-th hamburger shops (Note that |a| means the absolute value of a). Once a gate is set up between two shops, the i-th shop can instantly teleport hamburger to the j-th shop, and vice versa. Once a teleportation gate is built, it can be used any number of times.

Due to financial constraints in the Hamburger Universe, please help them calculate the minimum total cost required to ensure that all N breakfast shop can transport hamburgers to any other shop through a series of teleportation gates.

Input

The first line contains a positive integer N.

Following that, there are N lines, each containing two integers x_i and yi.

• 1 ≤ N ≤ 1000
• 0 ≤ x_i, y_i ≤ 5000

There could be different shops located at same coordinates.

Output

Output the answer in one line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given an array of n integers. Your task is to calculate the median of each window of k elements, from left to right.

The median is the middle element when the elements are sorted. If the number of elements is even, there are two possible medians and we assume that the median is the smaller of them.

Visualization of sample input:

[2 4 3] 5 8 1 2 1: 3
2 [4 3 5] 8 1 2 1: 4
2 4 [3 5 8] 1 2 1: 5
2 4 3 [5 8 1] 2 1: 5
2 4 3 5 [8 1 2] 1: 2
2 4 3 5 8 [1 2 1]: 1

Input

The first input line contains two integers n and k: the number of elements and the size of the window.

Then there are n integers x₁,x₂,…,x_n: the contents of the array.

- 1 <= k <= n <= 2 * 10⁵

- 1 <= x_i <= 10⁹

Output

Print n−k+1 values: the medians.

Please append a space after each number, and add a newline at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

DGL enjoys digging pits in a courtyard and filling them with water to create water pits. The courtyard is represented as a N x M matrix where each cell can be either a dirt mound "0" or a water pit "1". Water pit cells connected in any of the four directions (up, down, left, right) form a single water pit.

Your task is to:

1. Count the number of water pits.
2. Find the size of the largest water pit.

DGL will also specify changes to turn water pits into dirt mounds K times. Each change might disconnect water pits, affecting their size and count. You need to calculate the number of water pits and the largest water pit size after each change.

Input

The first line contains three integers N, M, and K.

The next N lines contain M integers (0, 1), representing the initial courtyard.

The next K lines contains 2 integers x, y, pair (x, y) representing a position to turn from a water pit into a dirt mound. Each specified position is guaranteed to be a water pit initially.

• 1 ≤ N * M ≤ 10⁶
• 1 ≤ K ≤ N * M
• 1 ≤ x ≤ N
• 1 ≤ y ≤ M

Subtask

For testcases 1 ~ 2: guarantee that N = 1.

Output

You need to print K + 1 line.

For the initial courtyard and each change, output two integers in one line seperate by a space:

1. The size of the largest water pit after the change.
2. The number of water pits after the change.

Sample Input  Download

Sample Output  Download

Tags

Discuss