문제를 푸는 문제 (Dequery)
시간 제한1초메모리 제한512 MB
같은 값을 여러 번 양쪽 끝에 넣고 여러 개를 빼며 k번째 원소를 읽는 질의를 처리해, 각 읽기 질의의 답을 출력한다.
문제
이 문제에는 제출할 수 없다. "문제를 푸는 문제" 문제를 참조하라.
비어 있는 덱(deque) Q가 주어진다. 쿼리를 Q번 실행하는 프로그램을 작성하시오. 쿼리는 다음 중 하나의 형태를 가진다.
- 1 x k: 덱의 맨 앞에 정수 x를 k번 삽입한다.
- 2 x k: 덱의 맨 뒤에 정수 x를 k번 삽입한다.
- 3 k: 덱의 맨 앞에서부터 k개의 수를 제거한다.
- 4 k: 덱의 맨 뒤에서부터 k개의 수를 제거한다.
- 5 k: 덱의 맨 앞에서부터 k번째에 있는 수를 출력한다.
입력
첫 줄에는 쿼리의 개수 Q가 주어진다. (Q ≤ 100,000) 다음 줄부터 한 줄에 하나씩 쿼리가 주어진다.
1, 2번 쿼리에서 1 ≤ x, k ≤ 109이다.
3, 4, 5번 쿼리에서 k는 1 이상이고, 현재 덱에 들어있는 수의 개수보다 작거나 같다.
5번 쿼리는 적어도 한 번 주어진다.
출력
각 5번 쿼리마다 정답을 한 줄씩 출력한다.