#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;
}