Monocarp has just learned a new card trick, and can't wait to present it to you. He shows you the entire deck of $n$ cards. You see that the values of cards from the topmost to the bottommost are integers $a_1, a_2, \dots, a_n$, and all values are different.

Then he asks you to shuffle the deck $m$ times. With the $j$-th shuffle, you should take $b_j$ topmost cards and move them under the remaining $(n - b_j)$ cards without changing the order.

And then, using some magic, Monocarp tells you the topmost card of the deck. However, you are not really buying that magic. You tell him that you know the topmost card yourself. Can you surprise Monocarp and tell him the topmost card before he shows it?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of cards in the deck.

The second line contains $n$ pairwise distinct integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the values of the cards.

The third line contains a single integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of shuffles.

The fourth line contains $m$ integers $b_1, b_2, \dots, b_m$ ($1 \le b_j \le n - 1$) — the amount of cards that are moved on the $j$-th shuffle.

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$. The sum of $m$ over all testcases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each testcase, print a single integer — the value of the card on the top of the deck after the deck is shuffled $m$ times.


-----Examples-----

Input
3
2
1 2
3
1 1 1
4
3 1 4 2
2
3 1
5
2 1 5 4 3
5
3 2 1 2 1
Output
2
3
3


-----Note-----

In the first testcase, each shuffle effectively swaps two cards. After three swaps, the deck will be $[2, 1]$.

In the second testcase, the second shuffle cancels what the first shuffle did. First, three topmost cards went underneath the last card, then that card went back below the remaining three cards. So the deck remained unchanged from the initial one — the topmost card has value $3$.

Difficulty: EASY
Tags: Mathematics

Implementation

Starter code:

Solutions:
import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')

def solve():
	for _ in range(get_int()):
		n = get_int()
		arr = get_list()
		m = get_int()
		op = get_list()
		get_print_int(arr[sum(op) % n])
solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	B = sum(b) % n
	print(a[B])


from sys import stdin
from math import log, floor, ceil, gcd
input = stdin.readline
inp = lambda : int(stdin.readline())

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		n = inp()
		a = ra(int)
		m = inp()
		b = sum(ra(int))
		print(a[b % n])
main()


from collections import deque

def main():
	for _ in range(int(input())):
		problem()

def problem():
	n = int(input())
	cards = deque(map(int, input().split()))
	m = int(input())
	total_shufs = sum(map(int, input().split())) % n
	cards.rotate(-total_shufs)
	print(cards[0])
import sys
input = sys.stdin.readline
exit(main())


import sys
input = sys.stdin.readline

def get_top(n: int, arra: list, m: int, arrb: list) -> str:
	return str(arra[sum(arrb) % n])
t = int(input())
result = ''
for _ in range(t):
	n = int(input())
	arra = list(map(int, input().split()))
	m = input()
	arrb = list(map(int, input().split()))
	result += get_top(n, arra, m, arrb) + '\n'
print(result[:-1])


import sys

def rall():
	return sys.stdin.readlines()

def rl():
	return sys.stdin.readline().strip()

def rl_types(types):
	str_list = [x for x in sys.stdin.readline().strip().split(' ')]
	return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
	sys.stdout.write(str(something) + '\n')

def pra(array):
	sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
	return array
NT = int(rl())
for ti in range(NT):
	n = int(rl())
	array = list(map(int, rl().split(' ')))
	m = int(rl())
	shuffles = list(map(int, rl().split(' ')))
	tot_moved = sum(shuffles)
	pr(array[tot_moved % n])


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(N, A) = (int(input()), list(map(int, input().split())))
	(M, B) = (int(input()), list(map(int, input().split())))
	X = sum(B) % N
	print(A[X])


import sys

def play_card_Afirst(A, B):
	if max(A) >= max(B):
		return 'Alice'
	else:
		return 'Bob'

def play_card_Bfirst(A, B):
	if max(B) >= max(A):
		return 'Bob'
	return 'Alice'

def shuffle(va, n, vb):
	return va[sum(vb) % n]
r = int(sys.stdin.readline())
for j in range(r):
	n = int(sys.stdin.readline())
	va = [int(x) for x in sys.stdin.readline().split()]
	m = sys.stdin.readline()
	vb = [int(x) for x in sys.stdin.readline().split()]
	print(shuffle(va, n, vb))


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for i in range(t):
	n1 = inp()
	a = li()
	n2 = inp()
	b = li()
	s = sum(b)
	l = s % n1
	print(a[l])


t = int(input())
res = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	p = sum(b) % n
	res.append(a[p])
for i in range(t):
	print(res[i])


def solution(ns, bs):
	i = sum(bs) % len(ns)
	return ns[i]
T = int(input())
results = []
for n in range(T):
	_ = input()
	ns = list(map(int, input().split(' ')))
	_ = input()
	bs = list(map(int, input().split(' ')))
	results.append(solution(ns, bs))
for r in results:
	print(r)


import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = int(input())
	b = [int(x) for x in input().split()]
	print(a[sum(b) % n])


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	m = int(input())
	b = [int(i) for i in input().split()]
	bb = sum(b)
	bb = bb % n
	print(a[bb])


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	s = sum(b)
	print(a[s % n])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = sum(list(map(int, input().split())))
	if b >= n:
		print(a[b % n])
	else:
		print(a[b])


T = int(input())
for _ in range(T):
	input()
	cards = input().split()
	input()
	offset = sum((int(num) for num in input().split()))
	print(int(cards[offset % len(cards)]))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	print(a[sum(map(int, input().split())) % n])


for i in range(int(input())):
	lenn = int(input())
	cards = list(map(int, input().split()))
	shufs = int(input())
	amount = list(map(int, input().split()))
	summ = sum(amount)
	imp = summ % lenn
	print(cards[imp])


t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	cards = [int(x) for x in input().split()]
	m = int(input())
	s = [int(x) for x in input().split()]
	out += str(cards[sum(s) % n]) + '\n'
print(out)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = int(input())
	d = list(map(int, input().split()))
	e = sum(d)
	f = e % a
	print(b[f])


n = int(input())
for i in range(n):
	x = int(input())
	y = list(map(int, input().split()))
	z = int(input())
	a = list(map(int, input().split()))
	w = sum(a) % x + 1
	print(y[w - 1])


def solve():
	n = int(input())
	l = list(input().split())
	m = int(input())
	b = list(map(int, input().split()))
	k = sum(b) % n
	print(l[k])
t = int(input())
for j in range(t):
	solve()


t = input()
end_result = ''
for i in range(int(t)):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = int(input())
	b = [int(x) for x in input().split()]
	end_result += str(a[sum(b) % len(a)]) + '\n'
print(end_result[:-1])


n = int(input())
for i in range(n):
	num_an = int(input())
	an = list(map(int, input().strip().split()))
	num_bm = int(input())
	bm = list(map(int, input().strip().split()))
	c = sum(bm)
	d = c % num_an
	print(an[d])


output = []
for _ in range(int(input())):
	n = int(input())
	A = [int(x) for x in input().split()]
	m = int(input())
	B = tuple((int(x) for x in input().split()))
	output.append(A[sum(B) % n])
for _ in output:
	print(_)


import sys
input = lambda : sys.stdin.readline().strip()
for Homu in range(int(input())):
	n = int(input())
	cards = [int(i) for i in input().split()]
	m = int(input())
	shuffles = [int(i) for i in input().split()]
	total_shuffle = sum(shuffles)
	pos = total_shuffle % n
	print(cards[pos])


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	su = sum(b)
	print(a[su % n])


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	m = int(input())
	B = list(map(int, input().split()))
	offset = 0
	for num in B:
		offset += num
		offset %= n
	return arr[offset]
for _ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	m = int(input())
	brr = [int(x) for x in input().split()]
	s = sum(brr)
	print(arr[s % n])


def main():
	tests = int(input())
	for _id in range(tests):
		n = int(input())
		cards = list(map(int, input().split()))
		n_mix = int(input())
		mixes = list(map(int, input().split()))
		print(cards[sum(mixes) % n])
main()


t = int(input())
while t:
	n = int(input())
	a = [int(i) for i in input().split()]
	m = int(input())
	b = [int(i) for i in input().split()]
	s = sum(b)
	k = s % n
	print(a[k])
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = int(input())
	l1 = list(map(int, input().split()))
	x = sum(l1)
	print(l[x % n])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	s = sum(b)
	if s % len(a) == 0:
		print(a[0])
	else:
		k = s % len(a)
		print(a[k])


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	m = int(input())
	q = list(map(int, input().split()))
	x = sum(q)
	t = x % n
	print(p[t])


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	s = sum(b)
	rem = s % n
	print(a[rem])


n = int(input())
l3 = []
for i in range(n):
	l2 = []
	n = int(input())
	l2.append(n)
	l = [int(x) for x in input().split()]
	l2.append(l)
	m = int(input())
	l = [int(x) for x in input().split()]
	l2.append(l)
	l3.append(l2)
for i in l3:
	print(i[1][sum(i[2]) % i[0]])


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	t = sum(b) % n
	print(l[t])


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	n2 = int(input())
	l2 = list(map(int, input().split()))
	print(l[sum(l2) % n])


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	ml = list(map(int, input().split()))
	s = sum(ml)
	index = s % n
	print(a[index])


for i in range(int(input())):
	a = int(input())
	l1 = list(map(int, input().split()))
	b = int(input())
	l2 = list(map(int, input().split()))
	s = sum(l2) % a + 1
	print(l1[s - 1])


for _ in range(int(input())):
	x = int(input())
	zoop = list(map(int, input().split()))
	pnt = 0
	y = int(input())
	zoop2 = list(map(int, input().split()))
	pnt += sum(zoop2) + x
	if pnt >= x:
		pnt %= x
	print(zoop[pnt])


n = int(input())
for i in range(n):
	an = int(input())
	a = list(map(int, input().split()))
	bn = int(input())
	b = list(map(int, input().split()))
	print(a[sum(b) % an])


R = lambda : map(int, input().split())
(t,) = R()
while t:
	t -= 1
	(n,) = R()
	a = (*R(),)
	R()
	print(a[sum(R()) % n])


t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	k = sum(b)
	h = k - len(a)
	k = k % n
	print(a[k])


T = int(input())
for t in range(T):
	deck_len = int(input())
	deck = [int(x) for x in input().split()]
	shuffle_len = int(input())
	shuffle = [int(x) for x in input().split()]
	print(deck[sum(shuffle) % deck_len])


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = int(input())
	sh = list(map(int, input().split()))
	ad = sum(sh)
	k = ad % n
	print(l[k])


tt = int(input())
for i in range(tt):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	s = sum(b)
	print(a[s % n])


t = int(input())
for i in range(t):
	a = int(input())
	b = list(map(int, input().split()))
	c = int(input())
	d = list(map(int, input().split()))
	f = sum(d)
	g = (f + 1) % a
	print(b[g - 1])


x = int(input())
for i in range(x):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = map(int, input().split())
	sum1 = sum(b)
	sum1 %= n
	print(a[sum1])


for i in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	m = int(input())
	l2 = list(map(int, input().split()))
	s = 0
	for j in l2:
		s += j
	s = s % n
	print(l1[s])


for _ in range(int(input())):
	n = int(input())
	an = list(map(int, input().split()))
	m = int(input())
	am = list(map(int, input().split()))
	sm = sum(am)
	step = sm % n
	print(an[step])


for _ in range(int(input())):
	n = int(input())
	cards = list(map(int, input().split()))
	m = int(input())
	suff = sum(map(int, input().split()))
	print(cards[suff % n])


for i in range(int(input())):
	n = int(input())
	a = input().split()
	m = int(input())
	b = input().split()
	sum = 0
	for j in b:
		sum += int(j)
	sum = sum % n
	print(a[sum])


for i in range(int(input())):
	n = int(input())
	n_arr = list(map(int, input().split()))
	m = int(input())
	m_arr = list(map(int, input().split()))
	s = sum(m_arr) % n
	print(n_arr[s])


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	sumb = sum(b)
	f = sumb % n
	print(a[f])


inpCount = int(input())
for _ in range(inpCount):
	n = input()
	distInts = input().split(' ')
	m = int(input())
	cardsMoved = list(map(lambda x: int(x), input().split(' ')))
	print(distInts[sum(cardsMoved) % len(distInts)])


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = int(input())
	print(x[sum(map(int, input().split())) % n])


for i in range(int(input())):
	l = [input() for e in ' ' * 4]
	print(l[1].split()[sum(map(int, l[3].split())) % int(l[0])])


for i in range(int(input())):
	n_1 = int(input())
	l_1 = list(map(int, input().split()))
	n_2 = int(input())
	l_2 = list(map(int, input().split()))
	x = sum(l_2)
	print(l_1[x % n_1])


times = int(input())
for time in range(times):
	n = int(input())
	cards = input().split()
	m = int(input())
	shuffles = input().split()
	print(int(cards[sum((int(j) for j in shuffles)) % n]))


def get_top_element(ar, sh):
	n = len(ar)
	ix = 0
	for s in sh:
		ix += s
		ix = ix % n
	return ar[ix]
t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split(' ')))
	m = int(input())
	sh = list(map(int, input().split(' ')))
	print(get_top_element(ar, sh))


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split(' ')))
	s = int(input())
	si = list(map(int, input().split(' ')))
	sa = sum(si) % len(a)
	print(a[sa])


for _ in range(int(input())):
	input()
	cards = list(map(int, input().split()))
	input()
	shuffles = list(map(int, input().split()))
	print(cards[sum(shuffles) % len(cards)])


t = int(input())
for i in range(t):
	n = int(input())
	arrcard = list(map(int, input().split(' ')))
	m = int(input())
	arrshuff = list(map(int, input().split(' ')))
	bm = sum(arrshuff)
	y = bm % n
	print(arrcard[y])


p = int(input())
while p:
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	s = sum(b)
	s = s % n
	x = a[:s]
	y = a[s:]
	a = y + x
	print(a[0])
	p -= 1


import collections
import math
import sys
from queue import PriorityQueue
from random import randint
RANDOM = randint(1, 10 ** 9)

def main(testnumber):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	print(a[sum(b) % n])
t = int(input())
cnt = 1
while t > 0:
	main(cnt)
	cnt += 1
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	m = int(input())
	shuf = [int(x) for x in input().split()]
	total = sum(shuf) % n
	print(arr[total])


I = lambda : [*map(int, input().split())]
for _ in ' ' * I()[0]:
	n = I()[0]
	a = I()
	m = I()
	b = I()
	print(a[sum(b) % n])


def solve():
	ans = 0
	n = int(input())
	a = list(map(int, input().strip().split()))
	m = int(input())
	b = list(map(int, input().strip().split()))
	maxa = max(a)
	maxb = max(b)
	if maxa > maxb:
		print('Alice')
		print('Alice')
	elif maxa < maxb:
		print('Bob')
		print('Bob')
	else:
		print('Alice')
		print('Bob')

def sol():
	n = int(input())
	a = list(map(int, input().strip().split()))
	m = int(input())
	b = list(map(int, input().strip().split()))
	return a[sum(b) % n]
for _ in range(int(input())):
	print(sol())


for tcase in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = sum(map(int, input().split()))
	print(a[b % n])


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	shift = sum(b) % n
	print(a[shift])


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	m = int(input())
	l2 = list(map(int, input().split()))
	ans = 0
	for i in l2:
		ans += i
	index = ans % n
	print(l1[index])


t = int(input())
for j in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	b = list(map(int, input().split()))
	k = sum(b)
	print(a[k % n])


for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	m = int(input())
	y = list(map(int, input().split()))
	print(x[sum(y) % n])


T = int(input())
q = []
for i in range(T):
	n = int(input())
	n_data = [int(i) for i in input().split()]
	m = int(input())
	m_data = [int(i) for i in input().split()]
	q.append((n, n_data, m, m_data))

def solve(n, n_data, m, m_data):
	pos = 0
	for j in m_data:
		pos += j
		pos %= n
	print(n_data[pos])
for (n, n_data, m, m_data) in q:
	solve(n, n_data, m, m_data)


for _ in range(int(input())):
	a = int(input())
	l1 = list(map(int, input().split()))
	b = int(input())
	l2 = list(map(int, input().split()))
	m = sum(l2)
	print(l1[m % a])


x = int(input())
for i in range(x):
	n = int(input())
	li1 = list(map(int, input().split()))
	s = int(input())
	li2 = list(map(int, input().split()))
	t = sum(li2)
	print(li1[t % n])