Description

Figure 1 shows the structure of a station for train dispatching.

Figure 1

In this station, A is the entrance for each train and B is the exit. S is the transfer end. All single tracks are one-way, which means that the train can enter the station from A to S, and pull out from S to B. Note that the overtaking is not allowed. Because the compartments can reside in S, the order that they pull out at B may differ from that they enter at A. However, because of the limited capacity of S, no more that m compartments can reside at S simultaneously.

Assume that a train consist of n compartments labeled {1, 2, …, n}. A dispatcher wants to know whether these compartments can pull out at B in the order of {a1, a2, …, an} (a sequence). If can, in what order he should operate it?

Input

Two lines:

1st line: two integers n and m;

2nd line: n integers separated by spaces, which is a permutation of {1, 2, …, n}. This is a compartment sequence that is to be judged regarding the feasibility.

Output

If the sequence is feasible, output the sequence. “Push” means one compartment goes from A to S, while “pop” means one compartment goes from S to B. Each operation takes up one line.

If the sequence is infeasible, output a “no”.

Example 1

Input

5 2
1 2 3 5 4

Output

push
pop
push
pop
push
pop
push
push
pop
pop

Example 2

Input

5 5
3 1 2 4 5

Output

No

Restrictions

1 <= n <= 1,600,000

0 <= m <= 1,600,000

Time: 2 sec

Memory: 256 MB

描述

某列车调度站的铁道联接结构如Figure 1所示。

其中，A为入口，B为出口，S为中转盲端。所有铁道均为单轨单向式：列车行驶的方向只能是从A到S，再从S到B；另外，不允许超车。因为车厢可在S中驻留，所以它们从B端驶出的次序，可能与从A端驶入的次序不同。不过S的容量有限，同时驻留的车厢不得超过m节。

设某列车由编号依次为{1, 2, …, n}的n节车厢组成。调度员希望知道，按照以上交通规则，这些车厢能否以{a1, a2, …, an}的次序，重新排列后从B端驶出。如果可行，应该以怎样

的次序操作?

输入

共两行。

第一行为两个整数n，m。

第二行为以空格分隔的n个整数，保证为{1, 2, …, n}的一个排列，表示待判断可行性的驶出序列{a1，a2，…，an}。

输出

若驶出序列可行，则输出操作序列，其中push表示车厢从A进入S，pop表示车厢从S进入B，每个操作占一行。

若不可行，则输出No。

样例

见英文题面

限制

1 ≤ n ≤ 1,600,000

0 ≤ m ≤ 1,600,000

时间：2 sec

空间：256 MB

 1 #include<cstdio>
 2 #include<iostream>
 3 #define N 1700000
 4 using namespace std;
 5 
 6 int arr[N];
 7 int ans[N];
 8 int Stack[N],top=0;
 9 
10 int read()
11 {
12     int now=0;
13     char ch=getchar();
14     while(!(ch>='0'&&ch<='9'))ch=getchar();
15     while(ch>='0'&&ch<='9')
16     {
17         now=now*10+ch-'0';
18         ch=getchar();
19     }
20     return now;
21 }
22 
23 int main()
24 {
25     int n,m;
26     n=read();
27     m=read();
28     //scanf("%d %d",&n,&m);
29     for(int i=1;i<=n;i++)arr[i]=read();
30     //scanf("%d",&arr[i]);
31     
32     int now=1;
33     int c1=0;
34     
35     for(int i=1;i<=n;i++)
36     {
37         ans[c1++]=1;
38         Stack[top++]=i;
39         
40         if(top>m)break;
41         
42         while(top>0&&Stack[top-1]==arr[now])
43         {
44             ans[c1++]=2;
45             now++;
46             top--;
47         }
48     }
49     
50     if(top)
51     {
52         printf("No\n");
53         return 0;
54     }
55     
56     for(int i=0;i<c1;i++)
57     if(ans[i]==1)printf("push\n");
58     else
59     printf("pop\n");
60     return 0;
61 }