//数组模拟链表秒了
#include<bits/stdc++.h>
using namespace std;

int n,m;
struct soldier{
    int index;
    int pre;
    int nxt;
};

int main(){
    scanf("%d%d",&n,&m);
    vector<soldier> s(n+10);
    for(int i = 1; i <= n; i++){
        s[i].index = i;
        s[i].pre = i-1;
        s[i].nxt = i+1;
    }
    int ind;
    while(m--){
        //不断维护每个死去士兵的左节点和右节点
        scanf("%d",&ind);
        int nx = s[ind].nxt;
        int pr = s[ind].pre;
        s[pr].nxt = s[ind].nxt;
        s[nx].pre = s[ind].pre;
        if(s[ind].nxt > n && s[ind].pre < 1) printf("* *\n");
        else if(s[ind].nxt > n) printf("%d *\n",s[ind].pre);
        else if(s[ind].pre < 1) printf("* %d\n",s[ind].nxt);
        else printf("%d %d\n",s[ind].pre, s[ind].nxt);
    }
}

#include <cstdio>

const int MAXN = 1000010;

int e[MAXN], l[MAXN], r[MAXN], idx;
int pos[MAXN]; // 记录每个士兵对应的节点索引

void init() {
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

void insert(int a, int x) {
    e[idx] = x;
    l[idx] = a;
    r[idx] = r[a];
    l[r[a]] = idx;
    r[a] = idx++;
}

void remove(int a) {
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    init();
    
    int last = 0; // 初始左端点
    for (int i = 1; i <= n; ++i) {
        insert(last, i);
        pos[i] = idx - 1; // 当前插入的节点索引
        last = pos[i]; // 更新为最新插入的节点
    }
    
    while (m--) {
        int s;
        scanf("%d", &s);
        int a = pos[s];
        int left = l[a], right = r[a];
        
        if (left == 0) printf("* ");
        else printf("%d ", e[left]);
        
        if (right == 1) printf("*\n");
        else printf("%d\n", e[right]);
        
        remove(a); // 删除该士兵节点
    }
    
    return 0;
}