# 2019.8.15乘兴打Codeforces Round #569 (Div. 2)小记

C. Valeriy and Deque

time limit per test

6 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently, on the course of algorithms and data structures, Valeriy learned how to use a deque. He built a deque filled with nn elements. The ii-th element is aiai (ii = 1,2,…,n1,2,…,n). He gradually takes the first two leftmost elements from the deque (let's call them AA and BB, respectively), and then does the following: if A>BA>B, he writes AA to the beginning and writes BB to the end of the deque, otherwise, he writes to the beginning BB, and AA writes to the end of the deque. We call this sequence of actions an operation.

For example, if deque was [2,3,4,5,1][2,3,4,5,1], on the operation he will write B=3B=3 to the beginning and A=2A=2 to the end, so he will get [3,4,5,1,2][3,4,5,1,2].

The teacher of the course, seeing Valeriy, who was passionate about his work, approached him and gave him qq queries. Each query consists of the singular number mjmj (j=1,2,…,q)(j=1,2,…,q). It is required for each query to answer which two elements he will pull out on the mjmj-th operation.

Note that the queries are independent and for each query the numbers AA and BB should be printed in the order in which they will be pulled out of the deque.

Deque is a data structure representing a list of elements where insertion of new elements or deletion of existing elements can be made from both sides.

Input

The first line contains two integers nn and qq (2≤n≤1052≤n≤105, 0≤q≤3⋅1050≤q≤3⋅105) — the number of elements in the deque and the number of queries. The second line contains nn integers a1a1, a2a2, ..., anan, where aiai (0≤ai≤109)(0≤ai≤109) — the deque element in ii-th position. The next qqlines contain one number each, meaning mjmj (1≤mj≤10181≤mj≤1018).

Output

For each teacher's query, output two numbers AA and BB — the numbers that Valeriy pulls out of the deque for the mjmj-th operation.

Examples

input

Copy

```5 3
1 2 3 4 5
1
2
10```

output

Copy

```1 2
2 3
5 2```

input

Copy

```2 0
0 0```

output

Copy

Note

1. Consider all 10 steps for the first test in detail:
2. [1,2,3,4,5][1,2,3,4,5] — on the first operation, AA and BB are 11 and 22, respectively. So, 22 we write to the beginning of the deque, and 11 — to the end. We get the following status of the deque: [2,3,4,5,1][2,3,4,5,1].
3. [2,3,4,5,1]⇒A=2,B=3[2,3,4,5,1]⇒A=2,B=3.
4. [3,4,5,1,2][3,4,5,1,2]
5. [4,5,1,2,3][4,5,1,2,3]
6. [5,1,2,3,4][5,1,2,3,4]
7. [5,2,3,4,1][5,2,3,4,1]
8. [5,3,4,1,2][5,3,4,1,2]
9. [5,4,1,2,3][5,4,1,2,3]
10. [5,1,2,3,4][5,1,2,3,4]
11. [5,2,3,4,1]⇒A=5,B=2[5,2,3,4,1]⇒A=5,B=2.

```#include<bits/stdc++.h>
#define rg register long long
#define inf 21474899993647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 100005
#define endl "\n"
#define   N 6000
const double eps=1e-8;
using namespace std;
{
char ch=getchar();
ll s=0,w=1;
while(ch<48||ch>57)
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch>=48&&ch<=57)
{
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*w;
}
inline void write(ll x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+48);
}
map<ll,pair<ll,ll>>p;
deque<ll>q;
int main()
{
for(rg i=1;i<=n;i++)
{
q.push_back(x);
}
for(rg i=1;i<=300000;i++)
{
ll a=q.front();
q.pop_front();
ll  b=q.front();
q.pop_front();
if(a>b)
{
q.push_front(a);
q.push_back(b);
}
else
{
q.push_front(b);
q.push_back(a);
}

p[i]=make_pair(a,b);
}
for(rg i=1;i<=t;i++)
{
if(x>2*n-2)
{
ll k=x-(2*n-2);
x=(k-1)%(n-1)+1+n-1 ;
}
cout<<p[x].first<<" "<<p[x].second<<endl;
}

return 0;
}```

0 条评论

• ### PAT (Advanced Level) Practice 1099 Build A Binary Search Tree （30 分）

A Binary Search Tree (BST) is recursively defined as a binary tree which has the...

• ### Codeforces Beta Round #51 C. Pie or die（博弈 思维）

Volodya and Vlad play the following game. There are k pies at the cells of n  × ...

• ### PAT (Advanced Level) Practice 1096 Consecutive Factors (20 分)

Among all the factors of a positive integer N, there may exist several consecuti...

• ### ABAP如何在调试查看EXPORT/IMPORT 内存数据

These memory IDs can be accessed in the debugger, but the option isn't accessibl...

• ### CodeForces 665B Shopping

B. Shopping time limit per test 1 second memory limit per test 256 megabyt...

• ### Code forces 719A Vitya in the Countryside

A. Vitya in the Countryside time limit per test:1 second memory limit per test:2...

• ### hdu----(1950)Bridging signals(最长递增子序列 (LIS) )

Bridging signals Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 65536/3...

• ### Codeforces 1291 Round #616 (Div. 2) C. Mind Control（超级详细）

You and your n−1 friends have found an array of integers a1,a2,…,an. You have de...

• ### 论综合 | 是什么让一个数字前端实现硅农开始学习Floorplan 的？

如题，是什么让一个数字前端实现硅农开始学习Floorplan 的？是制造工艺的进步，是实现方法学的被迫更新，是养家糊口生的本能，正可谓：头发落完终不悔，为伊消得...

• ### How to find “hidden” remote jobs using Google Search.

By using a special search operator with Google search, you can find remote jobs ...