You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

陶陶刚学了数组，并且他对查找一维数组中的最大值特别感兴趣，于是，他就产生了疑问：能不能找到数组中某个元素的 左边的最大值、右边的最大值和 不包含自身的最大值。

例如： 一个数组 共8个元素，

1 3 7 8 4 3 6 1

第 5个数（4） 左边的最大值是 8 右边最大值 是6，不包含自身的最大值 是 8

Input Format

第一行为 n,k(n表示数组含有n个元素,k表示有k次查询) (n<=500000;k<=50000)

第二行为 n个整数,表示数组的n个元素

第三行为 k个整数 表示对数组的k次查询

Output Format

n行整数,每行三个整数分别为: 左边最大值, 右边最大值 , 不包含自身的最大值

Sample

input

8 2
1 3 7 8 4 3 6 1
5 7

output

8 6 8
8 1 8

Hint

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$