Sereja loves number sequences very much. That's why he decided to make himself a new one following a certain algorithm.

Sereja takes a blank piece of paper. Then he starts writing out the sequence in m stages. Each time he either adds a new number to the end of the sequence or takes l first elements of the current sequence and adds them c times to the end. More formally, if we represent the current sequence as a_1, a_2, ..., a_{n}, then after we apply the described operation, the sequence transforms into a_1, a_2, ..., a_{n}[, a_1, a_2, ..., a_{l}] (the block in the square brackets must be repeated c times). 

A day has passed and Sereja has completed the sequence. He wonders what are the values of some of its elements. Help Sereja.


-----Input-----

The first line contains integer m (1 ≤ m ≤ 10^5) — the number of stages to build a sequence. 

Next m lines contain the description of the stages in the order they follow. The first number in the line is a type of stage (1 or 2). Type 1 means adding one number to the end of the sequence, in this case the line contains integer x_{i} (1 ≤ x_{i} ≤ 10^5) — the number to add. Type 2 means copying a prefix of length l_{i} to the end c_{i} times, in this case the line further contains two integers l_{i}, c_{i} (1 ≤ l_{i} ≤ 10^5, 1 ≤ c_{i} ≤ 10^4), l_{i} is the length of the prefix, c_{i} is the number of copyings. It is guaranteed that the length of prefix l_{i} is never larger than the current length of the sequence.

The next line contains integer n (1 ≤ n ≤ 10^5) — the number of elements Sereja is interested in. The next line contains the numbers of elements of the final sequence Sereja is interested in. The numbers are given in the strictly increasing order. It is guaranteed that all numbers are strictly larger than zero and do not exceed the length of the resulting sequence. Consider the elements of the final sequence numbered starting from 1 from the beginning to the end of the sequence.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Output-----

Print the elements that Sereja is interested in, in the order in which their numbers occur in the input. 


-----Examples-----
Input
6
1 1
1 2
2 2 1
1 3
2 5 2
1 4
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Output
1 2 1 2 3 1 2 1 2 3 1 2 1 2 3 4

Difficulty: MEDIUM_HARD
Tags: Sorting

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
from bisect import bisect_left

def fun(ind, alr, ll, sll):
	if ind in alr:
		return alr[ind]
	k = bisect_left(sll, ind)
	md = ll[k]
	return fun((ind - sll[k]) % md, alr, ll, sll)
pos = {}
m = int(input())
l = 0
cp = []
cpl = []
for _ in range(0, m):
	q = [int(i) for i in input().split()]
	if q[0] == 1:
		pos[l] = q[1]
		l += 1
	else:
		cp.append(q[1])
		l += q[1] * q[2]
		cpl.append(l)
n = int(input())
qq = [int(i) - 1 for i in input().split()]
ans = [fun(i, pos, cp, cpl) for i in qq]
print(*ans)


n = int(input())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
m = int(input())
b = list([int(x) - 1 for x in input().split()])
c = []
now = 0
k = 0
ans = []
for i in range(n):
	t = a[i]
	if t[0] == 1:
		now += 1
		if len(c) < 100000:
			c.append(t[1])
		if k < m and b[k] == now - 1:
			ans.append(t[1])
			k += 1
	else:
		last = now
		now += t[1] * t[2]
		while t[2]:
			if len(c) < 100000:
				c.extend(c[:t[1]])
			else:
				break
			t[2] -= 1
		while k < m and last <= b[k] < now:
			ans.append(c[(b[k] - last) % t[1]])
			k += 1
print(' '.join(map(str, ans)))


MAX_LEN = int(100000.0)
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
m = int(input())
b = list(map(lambda x: int(x) - 1, input().split()))
(curr, k, c, res) = (0, 0, [], [])
for i in range(n):
	t = a[i]
	last = curr
	if t[0] == 1:
		curr += 1
		if len(c) < MAX_LEN:
			c.append(t[1])
		if k < m and b[k] == curr - 1:
			res.append(t[1])
			k += 1
	else:
		curr += t[1] * t[2]
		while t[2] > 0 and len(c) < MAX_LEN:
			c.extend(c[:t[1]])
			t[2] -= 1
		while k < m and last <= b[k] < curr:
			res.append(c[(b[k] - last) % t[1]])
			k += 1
print(' '.join(map(str, res[:m])))


bot = True
from bisect import bisect_left
m = int(input())
(t, s) = ([input().split() for i in range(m)], [0] * m)
(l, n) = (0, int(input()))
for (j, i) in enumerate(t):
	l += 1 if i[0] == '1' else int(i[1]) * int(i[2])
	(t[j], s[j]) = (l, i[1] if i[0] == '1' else int(i[1]))
F = {}

def f(i):
	if not i in F:
		k = bisect_left(t, i)
		F[i] = s[k] if type(s[k]) == str else f((i - t[k] - 1) % s[k] + 1)
	return F[i]
print(' '.join((f(i) for i in map(int, input().split()))))


from bisect import bisect_left
m = int(input())
lines = []
for i in range(m):
	lines.append(list(map(int, input().split())))
n = int(input())
lengths = list(map(int, input().split()))
acc_lengths = [0]
for l in lines:
	acc_lengths.append(acc_lengths[-1] + (1 if l[0] == 1 else l[1] * l[2]))
result = {}

def find_number(l):
	if l not in result:
		i = bisect_left(acc_lengths, l) - 1
		result[l] = lines[i][1] if lines[i][0] == 1 else find_number((l - acc_lengths[i] - 1) % lines[i][1] + 1)
	return result[l]
print(' '.join([str(find_number(l)) for l in lengths]))


from sys import stdin
import os
debug = False
try:
	if os.environ['COMPUTERNAME'] == 'KRUEGER-PC':
		debug = True
except KeyError:
	pass

def debug_print(*foo):
	if debug:
		print(foo)
debug_print('debug active')

def print_array(res, size):
	if size:
		print(len(res))
	print(' '.join(map(str, res)))

def input_int_tuple():
	return tuple([x for x in map(int, stdin.readline().split())])

def input_int_array(size=True):
	if size:
		values = stdin.readline().split()
		assert len(values) == 1
	return [x for x in map(int, stdin.readline().split())]

def input_string():
	return stdin.readline()

def slen(s):
	if s[0] == 1:
		return 1
	if s[0] == 2:
		return s[1] * s[2]

def sget(s, n, pref, curlen):
	if s[0] == 1:
		return s[1]
	if s[0] == 2:
		d = n - curlen
		return pref[d % s[1]]
const_100k = 100000

def compute_prefix(stages):
	pref = []
	tr = 0
	split = 0
	for (i, s) in enumerate(stages):
		if s[0] == 1:
			pref.append(s[1])
		if s[0] == 2:
			l = s[1]
			c = s[2]
			if len(pref) + c * l > const_100k:
				c = (const_100k - len(pref)) // l + 1
				s[2] -= c
				if s[2] > 0:
					split = 1
			pref = pref + pref[:l] * c
			if len(pref) > const_100k:
				tr = i - split
				break
	stages = stages[tr + 1:]
	return (pref, stages)

def problem():
	(n,) = input_int_tuple()
	stages = []
	for s in range(n):
		stages.append(input_int_array(False))
	numbers = input_int_array()
	(pref, stages) = compute_prefix(stages)
	debug_print(len(pref))
	res = []
	curlen = len(pref)
	si = 0
	for x in numbers:
		i = x - 1
		if i < len(pref):
			res.append(pref[i])
		else:
			s = stages[si]
			while i >= curlen + slen(s):
				curlen += slen(s)
				si = si + 1
				s = stages[si]
			sym = sget(s, i, pref, curlen)
			res.append(sym)
	return res
print_array(problem(), False)


m = int(input())
(a, b, start, end) = ([], [], 0, 0)
idx = 0
for _ in range(m):
	line = list(map(int, input().split()))
	if line[0] == 1:
		x = line[1]
		start = end + 1
		end = end + 1
		if len(a) <= 100000:
			a.append(x)
		b.append((start, end, x))
	else:
		(l, c) = (line[1], line[2])
		start = end + 1
		end = end + l * c
		if len(a) <= 100000:
			for _ in range(c):
				a += a[:l]
				if len(a) > 100000:
					break
		b.append((start, end, l, c))
input()

def answer(n):
	global m, a, b, idx
	if n - 1 < len(a):
		return a[n - 1]
	while True:
		bi = b[idx]
		if bi[0] <= n <= bi[1]:
			break
		idx += 1
	if len(bi) == 3:
		return bi[2]
	n_bak = n
	n = (n - bi[0]) % bi[2] + 1
	return a[n - 1]
result = []
for n in map(int, input().split()):
	result.append('%s' % answer(n))
print(' '.join(result))


from sys import stdin
debug = False

def debug_print(*foo):
	if debug:
		print(foo)

def print_array(res, size):
	if size:
		print(len(res))
	print(' '.join(map(str, res)))

def input_int_tuple():
	return tuple([x for x in map(int, stdin.readline().split())])

def input_int_array(size=True):
	if size:
		values = stdin.readline().split()
		assert len(values) == 1
	return [x for x in map(int, stdin.readline().split())]

def slen(s):
	if s[0] == 1:
		return 1
	if s[0] == 2:
		return s[1] * s[2]

def sget(s, n, pref, curlen):
	if s[0] == 1:
		return s[1]
	if s[0] == 2:
		d = n - curlen
		return pref[d % s[1]]
const_100k = 100000

def compute_prefix(stages):
	pref = []
	tr = 0
	split = 0
	for (i, s) in enumerate(stages):
		if s[0] == 1:
			pref.append(s[1])
		if s[0] == 2:
			l = s[1]
			c = s[2]
			if len(pref) + c * l > const_100k:
				c = (const_100k - len(pref)) // l + 1
				s[2] -= c
				if s[2] > 0:
					split = 1
			pref = pref + pref[:l] * c
			if len(pref) > const_100k:
				tr = i - split
				break
	stages = stages[tr + 1:]
	return (pref, stages)

def problem():
	(n,) = input_int_tuple()
	sss = 0
	for x in range(const_100k * 20):
		sss += 1 * x
	if sss < 0:
		n = 10
	stages = []
	for s in range(n):
		stages.append(input_int_array(False))
	numbers = input_int_array()
	(pref, stages) = compute_prefix(stages)
	debug_print(len(pref))
	res = []
	curlen = len(pref)
	si = 0
	for x in numbers:
		i = x - 1
		if i < len(pref):
			res.append(pref[i])
		else:
			s = stages[si]
			while i >= curlen + slen(s):
				curlen += slen(s)
				si = si + 1
				s = stages[si]
			sym = sget(s, i, pref, curlen)
			res.append(sym)
	return res
print_array(problem(), False)


from bisect import bisect_left
m = int(input())
lines = []
for i in range(m):
	lines.append(list(map(int, input().split())))
n = int(input())
lengths = list(map(int, input().split()))
acc_lengths = [0]
for l in lines:
	acc_lengths.append(acc_lengths[-1] + (1 if l[0] == 1 else l[1] * l[2]))
seq = []
for l in lines:
	if l[0] == 1:
		seq.append(l[1])
	else:
		for i in range(l[2]):
			seq.extend(seq[:l[1]])
			if len(seq) >= 10 ** 5:
				break
	if len(seq) >= 10 ** 5:
		break

def find_number(l):
	if l <= len(seq):
		return seq[l - 1]
	i = bisect_left(acc_lengths, l) - 1
	return seq[(l - acc_lengths[i] - 1) % lines[i][1]]
print(' '.join([str(find_number(l)) for l in lengths]))


from sys import stdout, stdin, setrecursionlimit
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
from bisect import bisect_left
m = getInt()
(t, s) = ([getStrs() for i in range(m)], [0] * m)
(l, n) = (0, int(input()))
for (j, i) in enumerate(t):
	l += 1 if i[0] == '1' else int(i[1]) * int(i[2])
	(t[j], s[j]) = (l, i[1] if i[0] == '1' else int(i[1]))
F = {}

def f(i):
	if not i in F:
		k = bisect_left(t, i)
		F[i] = s[k] if type(s[k]) == str else f((i - t[k] - 1) % s[k] + 1)
	return F[i]
print(' '.join((f(i) for i in zzz())))