# 任务调度(Schedule)

### Description

Given initial priority setting of every task, your job is to predict the running order of a batch of tasks.

### Input

First line contains two integers, says n and m. n stands for the number of tasks in initial state. m stands for the length of predicted sequence. Every line is ended by a line break symbol. In each one of the following n lines, an integer and a string are included. This string is shorter than 8, which only contains lowercase letters and numbers. The integer is priority number and the string is the task name. The integer and string is separated by space.

### Output

At most m lines, each one contains a string. Output the name of tasks according to the order that tasks are executed. If the number of executed tasks is less than m, then output all the executed tasks.

### Example

Input

3 3
1 hello
2 world
10 test


Output

hello
hello
world


### Restrictions

0 <= n <= 4,000,000

0 <= m <= 2,000,000

0 < Priority number < 2^32

Time: 2 sec

Memory: 512 MB

Priority queue

### 限制

0 ≤ n ≤ 4,000,000

0 ≤ m ≤ 2,000,000

0 < 每个任务的初始优先级 < 2^32

### 提示

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104 #include #include #include #define INT_MAX 4294967296 #define Parent(x) x/2 #define LChild(x) x*2 #define RChild(x) x*2+1 using namespace std; struct task {     unsigned long long priority;     char name[10];     bool operator <(task b) {         if (priority < b.priority)             return true;         if (priority == b.priority) {             for (int i = 0; name[i] != '\0' && b.name[i] != '\0' && i < 10; i++) {                 if (name[i] != b.name[i])                     return name[i] < b.name[i];             }         }         return false;     }     bool operator >(task b) {         if (priority > b.priority)             return true;         if (priority == b.priority) {             for (int i = 0; name[i] != '\0' && b.name[i] != '\0' && i < 10; i++) {                 if (name[i] != b.name[i])                     return name[i] > b.name[i];             }         }         return false;     } }; template < typename T > class Heap {     public:         T arr[4000010];         int _size;         void swap(T & A, T & B) {             T C = A;             A = B;             B = C;         }         void makeHeap(int n) {             _size = n;             for (int i = n / 2; i > 0; i--) {                 perculateDown(i);             }         }         void perculateUp(int node) {             while (int parent = Parent(node)) {                 if (arr[parent] > arr[node]) {                     swap(arr[node],arr[parent]);                     node = parent;                 } else                     break;             }         }         void perculateDown(int node) {             while (int minChildNode =((RChild(node)) <=_size ? (arr[(LChild(node))] queue; int main() {     setvbuf(stdin,new char[1<<27],_IOFBF,1<<27);     setvbuf(stdout,new char[1<<27],_IOFBF,1<<27);     int n, m;     scanf("%d %d",&n,&m);     for (int i = 1; i <= n; i++) {         scanf("%lld %s",&queue.arr[i].priority,queue.arr[i].name);     }     queue.makeHeap(n);     while (m-- && queue._size) {         printf("%s\n",queue.getMin().name);         queue.DelAndInsertMin();     } }