Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Little Egor is a huge movie fan. He likes watching different kinds of movies: from drama movies to comedy movies, from teen movies to horror movies. He is planning to visit cinema this weekend, but he's not sure which movie he should watch.

There are n movies to watch during this weekend. Each movie can be characterized by two integers L_{i} and R_{i}, denoting the length and the rating of the corresponding movie. Egor wants to watch exactly one movie with the maximal value of L_{i} × R_{i}. If there are several such movies, he would pick a one with the maximal R_{i} among them. If there is still a tie, he would pick the one with the minimal index among them.

Your task is to help Egor to pick a movie to watch during this weekend.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases.

The first line of the test case description contains an integer n.

The second line of the test case description contains n integers L_{1}, L_{2}, ...,L_{n}. The following line contains n integers R_{1}, R_{2}, ..., R_{n}.

------ Output ------ 

For each test case, output a single integer i denoting the index of the movie that Egor should watch during this weekend. Note that we follow 1-based indexing.

------ Constraints ------ 

$1 ≤ T ≤ 5$
$1 ≤ n ≤ 100$
$1 ≤ L_{i}, R_{i} ≤ 100$

----- Sample Input 1 ------ 
2

2

1 2

2 1

4

2 1 4 1

2 4 1 4
----- Sample Output 1 ------ 
1

2
----- explanation 1 ------ 
In the first example case, both films have the same value of L × R, but the first film has a better rating.

In the second example case, the second and the fourth movies are equally good, but the second movie has a smaller index.

Difficulty: EASY
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	r = list(map(int, input().split(' ')))
	a = [l[i] * r[i] for i in range(n)]
	b = [i for i in range(n) if max(a) == l[i] * r[i]]
	c = [r[i] for i in b]
	print(r.index(max(c)) + 1)


goals = int(input())
for distractions in range(goals):
	aim = int(input())
	wife = list(map(int, input().split()))
	life = list(map(int, input().split()))
	(c, e, d) = (0, 0, 0)
	for death in range(aim):
		if life[death] * wife[death] > c:
			c = life[death] * wife[death]
			e = life[death]
			d = death + 1
		elif life[death] * wife[death] == c:
			if life[death] > e:
				d = death + 1
				e = life[death]
	print(d)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	l1 = []
	for i in range(n):
		l1.append(l[i] * r[i])
	m = max(l1)
	if l1.count(m) == 1:
		print(l1.index(m) + 1)
	else:
		l2 = []
		for i in range(len(l1)):
			if l1[i] == m:
				l2.append(r[i])
		m1 = max(l2)
		if l2.count(m1) == 1:
			print(r.index(m1) + 1)
		else:
			print(r.index(m1) + 1)


for i in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	R = list(map(int, input().split()))
	m = []
	c = 0
	for i in range(n):
		m.append(L[i] * R[i])
	for i in range(n):
		if m[i] == max(m):
			if R[i] > c:
				c = R[i]
	print(R.index(c) + 1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	temp = []
	te = 0
	fin = 0
	for j in range(n):
		temp.append(l[j] * r[j])
	if temp.count(max(temp)) == 1:
		print(temp.index(max(temp)) + 1)
	else:
		for j in range(n):
			if temp[j] == max(temp):
				if te < r[j]:
					te = r[j]
					fin = j + 1
		print(fin)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	l = list(map(int, sys.stdin.readline().split()))
	r = list(map(int, sys.stdin.readline().split()))
	v = 0
	ra = 0
	ind = 0
	for i in range(n):
		if l[i] * r[i] >= v:
			if r[i] > ra:
				ra = r[i]
				v = l[i] * r[i]
				ind = i + 1
	sys.stdout.write(str(ind) + '\n')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	p = [l[i] * r[i] for i in range(n)]
	a = max(p)
	b = max(r)
	if p.count(a) == 1:
		res = p.index(a)
	elif p.count(a) > 1 and r.count(b) == 1:
		res = r.index(b)
	elif r.count(b) > 1:
		res = r.index(b)
	print(res + 1)


for i in range(int(input())):
	n = int(input())
	L = list(map(int, input().split(' ')))
	R = list(map(int, input().split(' ')))
	(L1, L2, L3) = ([], [], [])
	for j in range(n):
		L1.append(L[j] * R[j])
	for j in range(n):
		if L1[j] == max(L1):
			L2.append(j)
	for j in L2:
		L3.append(R[j])
	print(R.index(max(L3)) + 1)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	j = i
	max1 = 0
	for i in range(len(l)):
		if r[i] * l[i] > max1:
			max1 = l[i] * r[i]
			e = r[i]
			j = i
		elif r[i] * l[i] == max1:
			if r[i] > e:
				e = r[i]
				j = i
	print(j + 1)


for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	R = list(map(int, input().split()))
	r = 0
	m = 0
	ind = 0
	indx = 0
	for (i, j) in zip(L, R):
		if i * j > m:
			m = i * j
			r = j
			indx = ind
		if i * j == m:
			if r < j:
				r = j
				indx = ind
		ind += 1
	print(indx + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	li = []
	for i in range(n):
		li.append(l[i] * r[i])
	ma = max(li)
	inde = []
	for j in range(n):
		if li[j] == ma:
			inde.append(r[j])
	m = max(inde)
	print(r.index(m) + 1)


for i in range(int(input())):
	n = int(input())
	length = [int(x) for x in input().split()]
	rating = [int(x) for x in input().split()]
	maxrating = 0
	index = 0
	rat = 0
	for i in range(n):
		if length[i] * rating[i] >= maxrating:
			maxrating = length[i] * rating[i]
			if rating[i] > rat:
				rat = rating[i]
				index = i + 1
	print(index)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	lr = []
	for i in range(len(l)):
		lr.append(l[i] * r[i])
	m = max(lr)
	rm = []
	rmi = []
	if lr.count(m) == 1:
		print(lr.index(m) + 1)
	elif r.count(max(r)) > 1:
		rmi.append(r.index(max(r)))
		print(min(rmi) + 1)
	else:
		print(r.index(max(r)) + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	result = [l[i] * r[i] for i in range(n)]
	max_val = max(result)
	for i in range(n):
		if result[i] != max_val:
			l[i] = 0
		else:
			l[i] = 1
	result = [l[i] * r[i] for i in range(n)]
	max_r = max(result)
	index = result.index(max_r)
	print(index + 1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	max1 = 0
	maxr = 0
	mini = n
	x = 0
	for j in range(n):
		x = l[j] * r[j]
		if max1 < x:
			max1 = x
	for j in range(n):
		if max1 == l[j] * r[j]:
			if maxr < r[j]:
				maxr = r[j]
	for j in range(n):
		if max1 == l[j] * r[j]:
			if maxr == r[j]:
				if mini > j:
					mini = j
	print(mini + 1)


t = int(input())
while t:
	t -= 1
	(c, d, e) = (0, 0, 0)
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		if a[i] * b[i] > c:
			d = i + 1
			c = a[i] * b[i]
			e = b[i]
		elif a[i] * b[i] == c:
			if b[i] > e:
				d = i + 1
				e = b[i]
	print(d)


T = int(input())
for _ in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	(a, c, d) = (0, 0, 0)
	for i in range(n):
		if l[i] * r[i] > a:
			a = l[i] * r[i]
			c = r[i]
			d = i + 1
		elif l[i] * r[i] == a:
			if r[i] > c:
				c = r[i]
				d = i + 1
	print(d)


for _ in range(int(input())):
	N = int(input())
	L = list((int(i) for i in input().split()))
	R = list((int(i) for i in input().split()))
	maxProd = 0
	index = 0
	rat = 0
	for i in range(N):
		if L[i] * R[i] >= maxProd:
			maxProd = L[i] * R[i]
			if R[i] > rat:
				rat = R[i]
				index = i + 1
	print(index)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	m = []
	for i in range(n):
		m.append(l[i] + r[i])
	print(m.index(max(m)) + 1)
	t -= 1


T = int(input())
for i in range(T):
	n = int(input())
	inp = input()
	inp_1 = input()
	list_L = inp.split(' ')
	list_R = inp_1.split(' ')
	for i in range(n):
		list_R[i] = int(list_R[i])
	for j in range(n):
		list_L[j] = int(list_L[j])
	count = 0
	res_list = []
	for m in range(n):
		res_list.append(list_L[m] * list_R[m])
	a = max(res_list)
	b = max(list_R)
	if res_list.count(a) == 1:
		res = res_list.index(max(res_list))
	elif res_list.count(a) > 1 and list_R.count(b) == 1:
		res = list_R.index(max(list_R))
	elif list_R.count(b) > 1:
		res = list_R.index(max(list_R))
	print(res + 1)


t = int(input())
while t:
	t -= 1
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	pmax = l1[0] * l2[0]
	rmax = l2[0]
	imax = 0
	for i in range(1, n):
		if pmax < l1[i] * l2[i]:
			pmax = l1[i] * l2[i]
			rmax = l2[i]
			imax = i
		elif pmax == l1[i] * l2[i]:
			if l2[i] > rmax:
				imax = i
				rmax = l2[i]
	print(imax + 1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	m = []
	max = 0
	max_rating = 0
	answer = 0
	for j in range(n):
		if l[j] * r[j] > max:
			max = l[j] * r[j]
			max_rating = r[j]
			answer = j + 1
		elif l[j] * r[j] == max:
			if r[j] > max_rating:
				max_rating = r[j]
				answer = j + 1
	print(answer)


for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	R = list(map(int, input().split()))
	c = 0
	A = [L[i] * R[i] for i in range(N)]
	ma = max(A)
	for i in range(N):
		if A[i] == ma:
			if R[i] > c:
				c = R[i]
	print(R.index(c) + 1)


from collections import Counter

def vmx(X):
	pmx = max(X)
	pC = Counter(X)
	index1 = pC[pmx]
	return (index1, X.index(pmx) + 1)
for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	R = list(map(int, input().split()))
	product = [l * r for (l, r) in zip(L, R)]
	(ind1, ind) = vmx(product)
	if ind1 == 1:
		print(ind)
		continue
	(ind2, ind) = vmx(R)
	if ind2 == 1:
		print(ind)
		continue
	print(R.index(max(R)) + 1)


T = int(input())
while T > 0:
	n = int(input())
	L = list(map(int, input().split()))[:n]
	R = list(map(int, input().split()))[:n]
	a = []
	p = 0
	for i in range(n):
		a.append(L[i] * R[i])
	for j in range(n):
		if a[j] == max(a):
			if R[j] > p:
				p = R[j]
	print(R.index(p) + 1)
	T -= 1


for i in range(int(input())):
	n = int(input())
	r = []
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	for i in range(n):
		r.append(x[i] * y[i])
	if r.count(max(r)) > 1:
		for i in range(n):
			if r[i] == max(r) and y[i] == max(y):
				print(i + 1)
				break
	else:
		print(r.index(max(r)) + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	s = []
	for i in range(n):
		s.append(l[i] * r[i])
	m = max(s)
	rm = []
	c = []
	for i in range(n):
		if s[i] == m:
			c.append(i)
	for i in c:
		rm.append(r[i])
	ir = r.index(max(rm))
	print(ir + 1)


for i in range(int(input())):
	l = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	m = a[0] * b[0]
	mi = 0
	for j in range(l):
		c = a[j] * b[j]
		if c > m:
			m = c
			mi = j
		elif c == m and b[j] > b[mi]:
			mi = j
	print(mi + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	a = []
	for i in range(n):
		a.append(l[i] * r[i])
	if a.count(max(a)) == n:
		print(r.index(max(r)) + 1)
	else:
		print(a.index(max(a)) + 1)


t = int(input())
while t != 0:
	n = int(input())
	k = []
	m = 0
	maxi = 0
	p = 0
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	for i in range(len(arr)):
		k.append(arr[i] * brr[i])
		if arr[i] * brr[i] >= maxi:
			maxi = arr[i] * brr[i]
			if brr[i] > m:
				m = brr[i]
				p = i + 1
	print(p)
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split(' ')))
	r = list(map(int, input().split(' ')))
	a = []
	c = 0
	for i in range(n):
		a.append(l[i] * r[i])
	for j in range(n):
		if a[j] == max(a):
			if r[j] > c:
				c = r[j]
	print(r.index(c) + 1)
	t = t - 1


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	c = 0
	k = []
	for i in range(len(r)):
		k.append(l[i] * r[i])
	for i in range(n):
		if k[i] == max(k):
			if r[i] > c:
				c = r[i]
	print(r.index(c) + 1)


for tc in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	ri = list(map(int, input().split()))
	arr = []
	arr2 = []
	for i in range(n):
		prod = li[i] * ri[i]
		arr.append(prod)
	count1 = arr.count(max(arr))
	if count1 == 1:
		print(arr.index(max(arr)) + 1)
	elif count1 > 1:
		if ri.count(max(ri)) == 1:
			print(ri.index(max(ri)) + 1)
		elif ri.count(max(ri)) > 1:
			print(ri.index(max(ri)) + 1)
		else:
			pass
	else:
		pass


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	k = []
	for i in range(a):
		k.append(l[i] * m[i])
	g = max(k)
	h = k.count(g)
	if h > 1:
		print(m.index(max(m)) + 1)
	else:
		print(k.index(g) + 1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	lr = []
	for j in range(n):
		lr.append(l[j] * r[j])
	c = max(lr)
	if lr.count(c) == 1:
		print(lr.index(c) + 1)
	elif lr.count(c) != 1:
		ra = 0
		index = 0
		for k in range(len(lr)):
			if lr[k] == c:
				if ra < r[k]:
					ra = r[k]
					index = k
		print(index + 1)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	a = []
	b = []
	for i in range(len(l)):
		x = l[i] * r[i]
		a.append(x)
		y = max(a)
	if a.count(y) == 1:
		print(a.index(y) + 1)
	elif a.count(y) > 1:
		if r.count(max(r)) == 1:
			print(r.index(max(r)) + 1)
		elif r.count(max(r)) > 1:
			b.append(r.index(max(r)))
			print(min(b) + 1)


for i in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	a = [l1[i] * l2[i] for i in range(n)]
	b = [i for i in range(n) if a[i] == max(a)]
	c = [l2[i] for i in b]
	print(l2.index(max(c)) + 1)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	s = 0
	for i in range(n):
		c.append(a[i] * b[i])
	for i in range(n):
		if c[i] == max(c):
			if b[i] > s:
				s = b[i]
	print(b.index(s) + 1)


for _ in range(int(input())):
	i = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	(c, e, d) = (0, 0, 0)
	for s in range(i):
		if x[s] * y[s] > c:
			c = x[s] * y[s]
			e = y[s]
			d = s + 1
		elif x[s] * y[s] == c:
			if y[s] > e:
				d = s + 1
				e = y[s]
	print(d)


for i in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	(val, r) = (0, 0)
	for (x, y) in zip(l1, l2):
		if x * y > val:
			val = x * y
			r = y
		elif x * y == val:
			if r < y:
				r = y
		else:
			continue
	print(l2.index(r) + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	pr = sorted([(i * j, j, k) for (k, i, j) in zip(range(1, n + 1), l, r)], key=lambda x: x[2])
	prs = sorted(pr, key=lambda x: x[1], reverse=True)
	print(sorted(prs, key=lambda x: x[0], reverse=True)[0][2])


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	k = []
	m = 0
	c = 0
	d = 0
	for i in range(len(arr)):
		if arr[i] * brr[i] >= m:
			m = arr[i] * brr[i]
			if brr[i] > d:
				d = brr[i]
				r = i + 1
	print(r)
	t = t - 1


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	r = list(map(int, input().split(' ')))
	maxnum = 0
	count = 0
	rnum = 0
	ind = 0
	for i in range(n):
		if maxnum < l[i] * r[i]:
			maxnum = l[i] * r[i]
	for j in range(n):
		if count > 2:
			break
		if maxnum == l[j] * r[j]:
			count += 1
			if rnum < r[j]:
				rnum = r[j]
				ind = j
	print(ind + 1)


T = int(input())
for i in range(T):
	N = int(input())
	L = list(map(int, input().split(' ', N)))
	R = list(map(int, input().split(' ', N)))
	movies = [L[j] * R[j] for j in range(N)]
	A = [k for k in range(N) if movies[k] == max(movies)]
	B = [R[l] for l in A]
	print(R.index(max(B)) + 1)


t = int(input())
while t > 0:
	x = int(input())
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	max = l[0] * m[0]
	index = 0
	MofI = m[0]
	for i in range(1, len(l)):
		if l[i] * m[i] > max:
			max = l[i] * m[i]
			index = i
			MofI = m[i]
		elif l[i] * m[i] == max and m[i] > MofI:
			max = l[i] * m[i]
			index = i
			MofI = m[i]
	print(index + 1)
	t -= 1


T = int(input())
for i in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	R = list(map(int, input().split()))
	x = []
	for i in range(N):
		x.append(L[i] * R[i])
	if x.count(max(x)) == N:
		print(R.index(max(R)) + 1)
	else:
		print(x.index(max(x)) + 1)


for i in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	s = 0
	ans = 0
	for i in range(n):
		x = arr1[i] * arr2[i]
		if s < x:
			s = x
			ans = i
		if s == x:
			if arr2[ans] < arr2[i]:
				ans = i
	print(ans + 1)


num_cases = int(input())
for i in range(num_cases):
	n = int(input())
	L = [int(x) for x in input().split()]
	R = [int(x) for x in input().split()]
	max_val = float('-inf')
	index = 0
	for j in range(n):
		val = L[j] * R[j]
		if val > max_val or (val == max_val and R[j] > R[index]) or (val == max_val and R[j] == R[index] and (j < index)):
			max_val = val
			index = j
	print(index + 1)


t = int(input())
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	c = list(map(lambda x, y: x * y, l1, l2))
	s = 0
	for i in range(n):
		if c[i] == max(c):
			if l2[i] > s:
				s = l2[i]
	print(l2.index(s) + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = list(map(int, input().split()))
	c = [l[i] * r[i] for i in range(n)]
	d = [i for i in range(n) if c[i] == max(c)]
	e = [r[i] for i in d]
	print(r.index(max(e)) + 1)


for i in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))[:n]
	R = list(map(int, input().split()))[:n]
	(a, b, c, d) = (0, 0, 0, 0)
	for j in range(n):
		if L[j] * R[j] > a:
			a = L[j] * R[j]
			b = R[j]
			c = d
		elif L[j] * R[j] == a:
			if R[j] > b:
				b = R[j]
				c = d
		d += 1
	print(c + 1)


for _ in range(int(input())):
	n = int(input())
	(a, b) = ([int(x) for x in input().split()], [int(x) for x in input().split()])
	m = a[0] * b[0]
	c = b[0]
	ans = 1
	for i in range(1, n):
		k = a[i] * b[i]
		if k > m:
			ans = i + 1
			c = b[i]
			m = k
		elif k == m and b[i] > c:
			ans = i + 1
			c = b[i]
	print(ans)