Bitland declared war on Chefland and sent an army to fight them, but Chefland defended efficiently and Bitland's army has been reduced to N$N$ soldiers. They have no chance of winning the war and do not want to surrender, so they are planning to commit group suicide. Josh, the leader of Bitland's remaining soldiers, has different plans — he wants to survive and somehow escape.
The soldiers are numbered 1$1$ through N$N$; Josh is soldier N$N$. The soldiers are going to stand in a circle in the order 1,2,…,P−1,N,P,P+1,…,N−1$1, 2, \ldots, P-1, N, P, P+1, \ldots, N-1$. Formally, they are standing in the circle in such a way that if Josh's position is P$P$ (1≤P≤N$1 \le P \le N$), then for each i$i$ (1≤i≤N−2$1 \le i \le N-2$, i≠P−1$i \neq P-1$), soldier i+1$i+1$ is directly to the right of soldier i$i$, soldier P$P$ (if P≤N−1$P \le N-1$) or 1$1$ (if P=N$P = N$) is directly to the right of Josh and Josh is directly to the right of soldier P−1$P-1$ (if P≥2$P \ge 2$) or soldier N−1$N-1$ (if P=1$P = 1$); if 2≤P≤N−2$2 \le P \le N-2$, soldier 1$1$ is also directly to the right of soldier N−1$N-1$. For each i$i$ (1≤i≤N−1$1 \le i \le N-1$), soldier i$i$ has a sword with power Ai$A_i$. Josh plans to take a shield with sufficiently high defense power D$D$.
First, the soldiers start to commit group suicide according to the following rules:
- Initially, soldier 1$1$ is the attacking soldier.
- If the attacking soldier is not Josh, this soldier attacks the soldier that is currently to his right.
- When Josh is attacked with power a$a$, the current defense power of his shield decreases by a$a$, and if it becomes negative, Josh dies. When a different soldier is attacked, he does not try to defend and dies immediately. The power of the attacking soldier's sword does not change.
- Then, the next living soldier to the right of the current attacking soldier becomes the attacking soldier and the process continues until there is only one soldier left.
It is clear that this way, Josh cannot be the last survivor. However, Chefland's general Chef plans to interrupt this process as soon as there are exactly two living soldiers of Bitland left (Josh wants to be one of them) by attacking them with Chefland's full firepower F$F$. Since this attack is unexpected, both attacked soldiers try to defend independently with the weapons they have. Josh survives if the current defense power of his shield is at least F$F$. Any other soldier survives only if the power of his sword is strictly greater than F$F$. Since Chefland does not attack again, if both Josh and another soldier survive, then the other soldier will kill Josh. Therefore, Josh wants to be the only survivor of Chefland's attack.
Your task is to find the minimum possible value of D$D$ such that Josh survives if he chooses his position P$P$ optimally (or determine that he cannot survive) and the lowest position P$P$ such that Josh survives if he takes a shield with this defense power D$D$.

-----Input-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first line of each test case contains a single integer N$N$.
- The second line contains N−1$N-1$ space-separated integers A1,A2,…,AN−1$A_1, A_2, \ldots, A_{N-1}$.
- The third line contains a single integer F$F$.

-----Output-----
For each test case, first, print a line containing the string "possible" if Josh can survive or "impossible" if he cannot (without quotes). Then, if he can survive, print a second line containing two space-separated integers P$P$ and D$D$.

-----Constraints-----
- 1≤T≤1,000$1 \le T \le 1,000$
- 2≤N≤1,000,000$2 \le N \le 1,000,000$
- 1≤Ai≤10,000$1 \le A_i \le 10,000$ for each valid i$i$
- 1≤F≤10,000$1 \le F \le 10,000$
- the sum of N$N$ over all test cases does not exceed 1,000,005$1,000,005$

-----Subtasks-----
Subtask #1 (30 points):
- 1≤T≤10$1 \le T \le 10$
- 2≤N≤100$2 \le N \le 100$
- 1≤Ai≤100$1 \le A_i \le 100$ for each valid i$i$
- 1≤F≤100$1 \le F \le 100$
Subtask #2 (70 points): original constraints

-----Example Input-----
2
5
12 34 45 5
10
5
10 15 43 20
5

-----Example Output-----
possible
4 100
impossible

-----Explanation-----
Example case 1: When Josh is at the position P=4$P = 4$, the soldiers' initial powers in clockwise order around the circle, starting with soldier 1$1$, are [12,34,45,D,5]$[12, 34, 45, D, 5]$ (D$D$ denotes Josh). Then, the following happens:
- The soldier with power 12$12$ attacks the soldier with power 34$34$ and kills him.
- The soldier with power 45$45$ attacks Josh, who defends. The living soldiers' powers are now [12,45,D−45,5]$[12, 45, D-45, 5]$ and Josh is the attacking soldier.
- Josh does not attack, so the soldier to his right (with power 5$5$) becomes the attacking soldier. He attacks the soldier with power 12$12$ and kills him.
- The soldier with power 45$45$ attacks Josh again and Josh defends again.
- The soldier with power 5$5$ attacks the soldier with power 45$45$ and kills him.
- Now, two soldiers are left: Josh (with a shield with defense power D−90$D-90$) and the soldier with a sword with power 5$5$. Each of them is attacked with firepower F=10$F=10$, so the power of Josh's shield drops to D−100$D-100$ and the other soldier dies.
If Josh survives, his shield's initial power D$D$ should be at least 45+45+10=100$45+45+10 = 100$. For all other positions P$P$, Josh cannot survive.
Example case 2: Regardless of how large D$D$ is and which position Josh chooses, after Chefland's attack, a soldier of Bitland other than Josh will always survive. This soldier will then attack Josh until his shield breaks and he dies.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics

Constructive algorithms


Solutions:
def fun(l, n, i):
	ans = 0
	no_term = n - i + 1 + i // 2
	side = i + (no_term - 1)
	if side > n:
		side = 2 * (side - n) - 1
	count = 0
	power = 1
	if i % 2 == 0:
		ans += l[side - 1]
	while side != i:
		if no_term % 2 == 0:
			no_term = no_term // 2
			power *= 2
		else:
			no_term = no_term // 2 + 1
			ans += l[side - 1]
			power *= 2
		side = i + (no_term - 1) * power
		if side > n:
			side = 2 * (side - n) - 1
	return ans
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	f = int(input())
	ans = []
	c = 0
	count = 0
	P = None
	for i in range(len(l)):
		if l[i] <= f:
			c = 1
			if count == 0:
				count += 1
				D = fun(l, n - 1, i + 1)
				P = i + 1
			else:
				yt = fun(l, n - 1, i + 1)
				if yt < D:
					P = i + 1
					D = yt
	if c == 0:
		print('impossible')
	else:
		print('possible')
		print(P, D + f)


def solve_small(numbers, n, f):
	found = False
	min_shield = 0
	min_pos = 0
	for pos in range(n):
		next_pos0 = pos % (n - 1)
		if numbers[next_pos0] > f:
			continue
		new_numbers = [_ for _ in numbers]
		new_numbers.insert(pos, 0)
		curr_pos = 0
		while len(new_numbers) > 2:
			next_pos = (curr_pos + 1) % len(new_numbers)
			if new_numbers[next_pos] <= 0:
				new_numbers[next_pos] -= new_numbers[curr_pos]
			elif new_numbers[curr_pos] > 0:
				new_numbers.pop(next_pos)
			else:
				pass
			if curr_pos >= len(new_numbers) - 1:
				curr_pos = 0
			else:
				curr_pos += 1
		(shield, min_f) = (-min(new_numbers), max(new_numbers))
		if min_f > f:
			continue
		shield += f
		found = True
		if not min_shield or min_shield > shield:
			min_shield = shield
			min_pos = pos
	if found:
		print('possible')
		return (min_pos + 1, min_shield)
	else:
		print('impossible')
		return (0, 0)

def solve_med(numbers, n, f):
	min_shield = 0
	min_pos = 0
	left_numbers = []
	right_numbers = [0] + [_ for _ in numbers]
	for pos in range(0, n):
		right_numbers.pop(0)
		if pos % 2:
			left_numbers.append(numbers[pos - 1])
		next_pos0 = pos % (n - 1)
		if numbers[next_pos0] > f:
			continue
		shield = f
		if pos % 2:
			shield += numbers[pos - 1]
		new_numbers = right_numbers + left_numbers
		jos_pos = len(new_numbers)
		new_pos = jos_pos
		factor = 2
		while new_pos > 1:
			if new_pos % 2:
				number = new_numbers[get_prev_multiple(jos_pos, factor)]
				number2 = numbers[get_prev_multiple_2(n - 1, pos, factor)]
				shield += number
			new_pos = new_pos // 2 + new_pos % 2
			factor *= 2
		if not min_shield or shield < min_shield:
			min_shield = shield
			min_pos = pos + 1
	if min_shield:
		print('possible')
	else:
		print('impossible')
	return (min_pos, min_shield)

def get_prev_multiple_2(n, pos, f):
	left_numbers = (pos - 1) // 2
	right_numbers = n - pos
	total_numbers = left_numbers + right_numbers
	number = total_numbers - total_numbers % f
	if number >= right_numbers:
		number = number - right_numbers
		return 2 * number
	else:
		return pos + number

def get_prev_multiple(n, f):
	return n - 1 - (n - 1) % f

def get_input_line():
	return input()

def solve_big(numbers, n, f):
	min_shield = 0
	min_pos = 0
	for pos in range(0, n):
		next_pos0 = pos % (n - 1)
		if numbers[next_pos0] > f:
			continue
		shield = f
		if pos % 2:
			shield += numbers[pos - 1]
		jos_pos = (pos - 1) // 2 + n - pos
		new_pos = jos_pos
		factor = 2
		over = False
		while new_pos > 1:
			if new_pos % 2:
				number = numbers[get_prev_multiple_2(n - 1, pos, factor)]
				shield += number
				if min_shield and shield >= min_shield:
					over = True
					break
			new_pos = new_pos // 2 + new_pos % 2
			factor *= 2
		if over:
			continue
		if not min_shield or shield < min_shield:
			min_shield = shield
			min_pos = pos + 1
	if min_shield:
		print('possible')
	else:
		print('impossible')
	return (min_pos, min_shield)
t = int(input())
for i in range(t):
	n = int(input())
	numbers = list(map(int, input().split(' ')))
	f = int(input())
	(min_pos, min_shield) = solve_med(numbers, n, f)
	if min_shield:
		print(min_pos, min_shield)


import math
from copy import copy

def nextPowerOf2(n):
	n -= 1
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n += 1
	return n

def safeind(n):
	p = nextPowerOf2(n)
	m = (p - 1 - n) * 2
	ans = p - 1 - m
	return ans

def cal(l, idx, f, N):
	l.insert(idx, f)
	temp = l[:idx:2]
	l = l[idx:] + temp
	pos = N - idx
	k = []
	if len(temp) > 0 and idx % 2 != 0:
		l[0] += temp[-1]
		k.append(temp[-1])
	while len(l) > 2:
		if len(l) % 2 == 0:
			l[0] += l[-1]
			k.append(l[-1])
		l = [l[0]] + l[1:N:2]
	return l[0]
try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		f = int(input())
		pos = []
		for i in range(n - 1):
			if arr[i] <= f:
				pos.append(i)
		if len(pos) == 0:
			print('impossible')
			continue
		ans = safeind(n - 1)
		if ans - 1 in pos:
			print('possible')
			print(ans, f)
		else:
			D = math.inf
			for i in pos:
				l = []
				for x in arr:
					l.append(x)
				temp = cal(l, i, f, n)
				if temp < D:
					D = temp
					posi = i + 1
			print('possible')
			print(posi, D)
except:
	pass


def solvebrute(a, f, n):
	(bestd, bestp) = (1000000000000000.0, -1)
	for p in range(1, n + 1):
		if a[(p - 1) % (n - 1)] > f:
			continue
		b = a[0:p - 1] + [-1] + a[p - 1:]
		jidx = p - 1
		alive = [1 for _ in range(n)]
		alive[jidx] = -1
		nalive = n - 1
		i = 0 if p != 1 else 1
		cd = 0
		while nalive != 1:
			killer = i
			i += 1
			i %= n
			while alive[i] == 0:
				i += 1
				i %= n
			killed = i
			if killed == jidx:
				cd += b[killer]
			else:
				alive[killed] = 0
				nalive -= 1
			i += 1
			i %= n
			while alive[i] == 0:
				i += 1
				i %= n
			if i == jidx:
				i += 1
				i %= n
				while alive[i] == 0:
					i += 1
					i %= n
		if cd + f < bestd:
			(bestd, bestp) = (cd + f, p)
	print(bestp, bestd)

def solve(a, f, n):
	for i in range(0, n - 1, 2):
		a.append(a[i])
	(bestp, bestd) = (-1, 10000000000.0)
	for p in range(1, n + 1):
		if a[p - 1] > f:
			continue
		cd = 0
		if p % 2 == 0:
			cd += a[p - 2]
		zeroidx = p - 1
		lastidx = n - 2 + p // 2
		m = lastidx - zeroidx + 2
		g = 2
		nelts = m - 1
		while m != 2:
			if m % 2 == 0:
				idx = nelts - nelts % g
				cd += a[zeroidx + idx]
			m = m // 2 + 1
			g <<= 1
		if cd + f < bestd:
			(bestd, bestp) = (cd + f, p)
	print(bestp, bestd)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = int(input())
	if all([ai > f for ai in a]):
		print('impossible')
	else:
		print('possible')
		if n == 2:
			print(1, f)
		elif n <= 200:
			solvebrute(a, f, n)
		else:
			solve(a, f, n)


import sys, os, re, random

def read_int():
	return int(input())

def read_int_list():
	return [int(x) for x in input().split()]

def read_str():
	return input().strip()

def read_str_list():
	return input().split()
T = read_int()
while T > 0:
	T -= 1
	n = read_int()
	a = read_int_list()
	f = read_int()
	(found, ans_d, ans_p) = (False, 0, 0)
	for p in range(n - 1):
		if a[p % (n - 1)] > f:
			continue
		d = f
		if p % 2 == 1:
			d += a[p - 1]
		c = p // 2 + p % 2 + (n - 1) - p
		x = 1
		while True:
			m = c // x + (0 if c % x == 0 else 1)
			if m <= 1:
				break
			if m % 2 == 1:
				l = p + (c // x - 1) * x + (0 if c % x == 0 else x)
				if l >= n - 1:
					l %= n - 1
					l += l
				d += a[l]
			x *= 2
			if found and d > ans_d:
				break
		if a[p] <= f:
			if not found or ans_d > d:
				found = True
				ans_p = p + 1
				ans_d = d
	if found:
		print('possible')
		print('{} {}'.format(ans_p, ans_d))
	else:
		print('impossible')


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		a1 = a.copy()
		f = int(input())
		length_a = len(a)
		l1 = []
		l2 = []
		for j in range(length_a + 1):
			a = a1.copy()
			l = ['D', 0, 0]
			a.insert(j, l)
			k = 0
			l[2] = j + 1
			while len(a) != 2:
				length = len(a)
				if k >= length:
					k = 0
				if a[k] == l:
					k = k + 1
					continue
				else:
					m = k + 1
					if m >= length:
						m = 0
					if a[m] == l:
						l[1] += a[k]
					else:
						del a[m]
					k += 1
			if a[0] == l:
				l[1] += f
			else:
				a[0] = a[0] - f
			if a[1] == l:
				l[1] += f
			else:
				a[1] = a[1] - f
			if a[0] != l:
				if a[0] <= 0:
					l1.append(l)
					l2.append(1)
				else:
					l2.append(0)
			if a[1] != l:
				if a[1] <= 0:
					l1.append(l)
					l2.append(1)
				else:
					l2.append(0)
		if len(l1) > 0:
			value = min(l1)
			print('possible')
			print(value[2], value[1])
		else:
			print('impossible')
except:
	pass


def fun(l, ptr, lr, a):
	c = 0
	add = []
	sq = 1
	while l > 1:
		if l % 2 != 0:
			add.append(sq * (l - 1))
			l = (l + 1) // 2
		else:
			l = l // 2
		c += 1
		sq *= 2
	ans = 0
	for i in range(len(add)):
		if add[i] < lr:
			add[i] += ptr
		else:
			add[i] = (add[i] - lr) * 2
		ans += a[add[i]]
	return ans
t = int(input())
for ij in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	f = int(input())
	less = []
	for i in range(n - 1):
		if a[i] <= f:
			less.append(i)
	if len(less) == 0:
		print('impossible')
	else:
		ans = 1000000000
		p = -1
		if len(less) < 700000:
			for i in range(len(less)):
				if i < 700000:
					tans = 0
					ptr = less[i]
					ll = 0
					lr = 0
					l = 0
					if less[i] % 2 != 0:
						tans += a[less[i] - 1]
						ll = (ptr + 1) // 2
					else:
						ll = ptr // 2
					lr = n - 1 - ptr
					l = lr + ll
					tans += fun(l, ptr, lr, a)
					if ans > tans:
						ans = tans
						p = less[i]
		else:
			c = 0
			i = len(less) - 1
			while i >= 0:
				c += 1
				if c < 700000:
					tans = 0
					ptr = less[i]
					ll = 0
					lr = 0
					l = 0
					if less[i] % 2 != 0:
						tans += a[less[i] - 1]
						ll = (ptr + 1) // 2
					else:
						ll = ptr // 2
					lr = n - 1 - ptr
					l = lr + ll
					tans += fun(l, ptr, lr, a)
					if ans > tans:
						ans = tans
						p = less[i]
				i -= 1
		print('possible')
		print(p + 1, ans + f)


from math import ceil, log
for T in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	F = int(input())
	possiblePositions = []
	for i in range(len(A)):
		if A[i] <= F:
			possiblePositions.append(i)
	if len(possiblePositions) == 0:
		print('impossible')
		continue
	minD = 10 ** 6
	N -= 1
	P = 2 ** ceil(log(N, 2))
	M = P - 1 - N
	M *= 2
	safePosition = P - 1 - M
	safePosition -= 1
	if safePosition in possiblePositions:
		print('possible')
		print(safePosition + 1, F)
		continue
	N += 1
	for p in possiblePositions:
		B = A.copy()
		B.insert(p, 'Josh')
		i = 0
		D = 0
		while len(B) > 2:
			if B[i] != 'Josh':
				if i == len(B) - 1:
					if B[0] == 'Josh':
						D += B[i]
					else:
						del B[0]
				elif B[i + 1] == 'Josh':
					D += B[i]
				else:
					del B[i + 1]
			if i >= len(B) - 1:
				i = 0
			else:
				i += 1
		if D < minD:
			minP = p
			minD = D
			if minD == F:
				break
	print('possible')
	print(minP + 1, minD + F)


def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		f = int(input())
		idxs = []
		i = 0
		while i < n - 1:
			if a[i] <= f:
				idxs.append(i)
			i += 1
		if len(idxs) == 0:
			print('impossible')
			continue
		mn = 1000000000
		for k in idxs:
			left = k
			pts = 0
			elm = left - 1
			right = n - 1 - left
			last = n - 2
			sub = a[elm]
			sleft = 1
			slast = 1
			while left > 0:
				if left % 2 == 0:
					elm -= sleft
					sub = a[elm]
					left = left // 2
					sleft *= 2
				else:
					pts += a[elm]
					left = (left + 1) // 2
					sleft *= 2
				if right % 2 == 0:
					last -= slast
					right //= 2
					slast *= 2
				else:
					slast *= 2
					left -= 1
					right = (right + 1) // 2
			while right > 2:
				if right % 2 == 0:
					last -= slast
					sub = a[last]
					right = right // 2
					slast *= 2
				else:
					slast *= 2
					sub = a[last]
					pts += sub
					right = (right + 1) // 2
			if mn > pts:
				mn = pts
				idx = k
				if pts == 0:
					break
		print('possible')
		print(idx + 1, mn + f)
main()


import numpy as np
for _ in range(int(input())):
	n = int(input()) - 1
	soldiers = [int(j) for j in input().split()]
	force = int(input())
	attacks = np.zeros(2 * n, dtype=int)
	attacks[:n] = np.array(soldiers)
	attacks[n:2 * n] = attacks[:n]
	shield = [0 for _ in range(n)]
	pow_of_2 = 1
	while n // pow_of_2 > 0:
		pow_of_2 *= 2
	soldier_of_attack = (2 * n - pow_of_2) % n
	pow_of_2 = attacks[soldier_of_attack] > force
	for i in range(n):
		if attacks[i] > force:
			shield[i] = 10 ** 11
		elif n == 1:
			shield[i] = force
		elif pow_of_2:
			shield[i] = force
			num_of_survivors = n
			soldiers = list(attacks[i:i + n])
			starting_soldier = (n - i) % n
			if (num_of_survivors - starting_soldier) % 2 == 1:
				shield[i] += soldiers[-1]
			soldiers = [soldiers[i] for i in range(num_of_survivors) if i < starting_soldier or (i - starting_soldier) % 2 == 0]
			num_of_survivors = starting_soldier + (num_of_survivors - starting_soldier - 1) // 2
			if num_of_survivors > 1:
				pow_2 = 1
				while True:
					attacker = num_of_survivors - num_of_survivors % pow_2
					pow_2 *= 2
					if attacker == 0:
						break
					if attacker % pow_2 == 0:
						shield[i] += soldiers[attacker]
		elif i == soldier_of_attack:
			shield[i] = force
		else:
			shield[i] = force + 1
	shield_needed = min(shield)
	if shield_needed == 10 ** 11:
		print('impossible')
	else:
		print('possible')
		for i in range(n):
			if shield[i] == shield_needed:
				print(str(i + 1) + ' ' + str(shield_needed))
				break


def func(pos, l, n):
	ptr = pos - 1
	ans = 0
	ele = n - 1
	left = True
	if pos % 2 == 1:
		ans += l[ptr]
	else:
		ptr = ptr - 1
	ele = ele - pos // 2
	mul = 1
	while ele > 1:
		if left:
			if ele % 2 == 0:
				ptr = ptr - mul * 2
				if ptr < 0:
					ptr = ptr + 2 * n - 2
					if ptr % 2 == 1:
						ptr -= 1
					ptr = ptr // 2
					left = False
			else:
				ans += l[ptr]
			ele = ele - ele // 2
			mul *= 2
		else:
			if ele % 2 == 0:
				ptr = ptr - mul
			else:
				ans = ans + l[ptr]
			ele = ele - ele // 2
			mul *= 2
	return ans
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	f = int(input())
	ans = 9999999999999999999999999999
	if n == 2:
		if l[0] <= f:
			ans = 0
			pos = 1
	else:
		for i in range(n - 1):
			if l[(i + 1) % (n - 1)] <= f:
				if ans == -1:
					ans = func(i + 1, l, n)
					pos = i + 2
					if pos == n:
						pos = 1
				else:
					temp2 = func(i + 1, l, n)
					if temp2 < ans:
						pos = i + 2
						ans = temp2
						if pos == n:
							pos = 1
					elif temp2 == ans:
						if i == n - 2:
							pos = 1
	if ans == 9999999999999999999999999999:
		print('impossible')
	else:
		print('possible')
		print(pos, ans + f)


def get_prev_multiple(n, f):
	return n - 1 - (n - 1) % f

def get_prev_multiple_2(n, pos, f):
	left_numbers = (pos - 1) // 2
	right_numbers = n - pos
	total_numbers = left_numbers + right_numbers
	number = total_numbers - total_numbers % f
	if number >= right_numbers:
		number = number - right_numbers
		return 2 * number
	else:
		return pos + number

def get_input_line():
	return input()

def solve_small(numbers, n, f):
	found = False
	min_shield = 0
	min_pos = 0
	for pos in range(n):
		next_pos0 = pos % (n - 1)
		if numbers[next_pos0] > f:
			continue
		new_numbers = [_ for _ in numbers]
		new_numbers.insert(pos, 0)
		curr_pos = 0
		while len(new_numbers) > 2:
			next_pos = (curr_pos + 1) % len(new_numbers)
			if new_numbers[next_pos] <= 0:
				new_numbers[next_pos] -= new_numbers[curr_pos]
			elif new_numbers[curr_pos] > 0:
				new_numbers.pop(next_pos)
			else:
				pass
			if curr_pos >= len(new_numbers) - 1:
				curr_pos = 0
			else:
				curr_pos += 1
		(shield, min_f) = (-min(new_numbers), max(new_numbers))
		if min_f > f:
			continue
		shield += f
		found = True
		if not min_shield or min_shield > shield:
			min_shield = shield
			min_pos = pos
	if found:
		print('possible')
		return (min_pos + 1, min_shield)
	else:
		print('impossible')
		return (0, 0)

def solve_med(numbers, n, f):
	min_shield = 0
	min_pos = 0
	left_numbers = []
	right_numbers = [0] + [_ for _ in numbers]
	for pos in range(0, n):
		right_numbers.pop(0)
		if pos % 2:
			left_numbers.append(numbers[pos - 1])
		next_pos0 = pos % (n - 1)
		if numbers[next_pos0] > f:
			continue
		shield = f
		if pos % 2:
			shield += numbers[pos - 1]
		new_numbers = right_numbers + left_numbers
		jos_pos = len(new_numbers)
		new_pos = jos_pos
		factor = 2
		while new_pos > 1:
			if new_pos % 2:
				number = new_numbers[get_prev_multiple(jos_pos, factor)]
				number2 = numbers[get_prev_multiple_2(n - 1, pos, factor)]
				shield += number
			new_pos = new_pos // 2 + new_pos % 2
			factor *= 2
		if not min_shield or shield < min_shield:
			min_shield = shield
			min_pos = pos + 1
	if min_shield:
		print('possible')
	else:
		print('impossible')
	return (min_pos, min_shield)

def solve_big(numbers, n, f):
	min_shield = 0
	min_pos = 0
	for pos in range(0, n):
		next_pos0 = pos % (n - 1)
		if numbers[next_pos0] > f:
			continue
		shield = f
		if pos % 2:
			shield += numbers[pos - 1]
		jos_pos = (pos - 1) // 2 + n - pos
		new_pos = jos_pos
		factor = 2
		over = False
		while new_pos > 1:
			if new_pos % 2:
				number = numbers[get_prev_multiple_2(n - 1, pos, factor)]
				shield += number
				if min_shield and shield >= min_shield:
					over = True
					break
			new_pos = new_pos // 2 + new_pos % 2
			factor *= 2
		if over:
			continue
		if not min_shield or shield < min_shield:
			min_shield = shield
			min_pos = pos + 1
	if min_shield:
		print('possible')
	else:
		print('impossible')
	return (min_pos, min_shield)

def main():
	t = int(get_input_line())
	for i in range(t):
		n = int(get_input_line())
		numbers = list(map(int, get_input_line().split()))
		f = int(get_input_line())
		(min_pos, min_shield) = solve_big(numbers, n, f)
		if min_shield:
			print(min_pos, min_shield)

def _check_differences(n, tests=100, m=10):
	import random
	for i in range(tests):
		numbers = [random.randint(1, m) for _ in range(n)]
		f = random.randint(1, m)
		rb = solve_med(numbers, n + 1, f)
		rs = solve_big(numbers, n + 1, f)
		if rs != rb:
			print(numbers, rs, rb, f)
			exit()
main()


p2 = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216]
for _ in range(int(input())):
	n = int(input()) - 1
	a = [int(x) for x in input().split()]
	(f, l) = (int(input()), [])
	for i in range(n):
		if a[i] <= f:
			l.append(i)
		if i % 2 == 0:
			a.append(a[i])
	if len(l) == 0:
		print('impossible')
		continue
	print('possible')
	(d, p) = (10 ** 12, -1)
	for i in l:
		x = -1 + n - i + (i + 1) // 2
		last = i + x
		td = f
		if i % 2 == 1:
			td += a[i - 1]
		for j in range(1, 25):
			if p2[j] > x:
				break
			la = last - x % p2[j]
			if la + p2[j - 1] > last:
				td += a[la]
		if td < d:
			(d, p) = (td, i + 1)
	print(p, d)


t = int(input())
while t > 0:
	n = int(input()) - 1
	soldier = list(map(int, input().split()))
	f = int(input())
	if min(soldier) > f:
		print('impossible')
	else:
		print('possible')
		(p, d) = (0, 250000)
		power = 0
		while n > 1:
			n //= 2
			power += 1
		n = len(soldier)
		pos = n - 2 ** power
		if soldier[pos + pos] <= f:
			p = pos + pos
			d = 0
		else:
			for i in range(len(soldier)):
				if soldier[i] <= f:
					temp = soldier.copy()
					temp.insert(i, 0)
					ans = 0
					if i % 2 != 0:
						ans += temp[i - 1]
					del temp[1:i:2]
					left = i - i // 2
					temp = temp[left:] + temp[:left]
					while len(temp) > 2:
						if len(temp) % 2 == 0:
							ans += temp[-1]
							if d <= ans:
								break
						del temp[2::2]
					if d > ans:
						d = ans
						p = i
					if d == 0:
						break
		print(p + 1, d + f)
	t -= 1


t = int(input())
while t > 0:
	n = int(input()) - 1
	l = list(map(int, input().split()))
	f = int(input())
	flag = 0
	dmin = 10 ** 9
	for i in range(n):
		if l[i] <= f:
			flag = 1
			nlv = (i + 1) // 2
			if nlv == 0:
				nla = 0
			else:
				nla = nlv * 2 - 1
			nr = n - i
			n2 = nr + nlv
			if i % 2 == 0:
				d = f
			else:
				d = l[i - 1] + f
			a = 2
			n3 = n2
			p = i + 1
			while n3 > 1:
				if (n2 - 1) % a == 0:
					d += l[(i + nr + nla - 1) % n]
					if d >= dmin:
						break
				else:
					diff = a // 2
					n2 = n2 - a // 2
					if nlv >= diff:
						nlv -= diff
					else:
						diff -= nlv
						nr -= diff
						nlv = 0
					if nlv == 0:
						nla = 0
					else:
						nla = nlv * 2 - 1
				n3 = (n3 + 1) // 2
				a = a * 2
			if d < dmin:
				dmin = d
				pos = p
	if flag == 0:
		print('impossible')
	else:
		print('possible')
		print(pos, dmin)
	t -= 1


import math

def validate(n, i):
	n.insert(i, 0)
	i = 0
	while len(n) > 2:
		pop_flag = True
		while i < len(n):
			if i == len(n) - 1:
				pop_flag = False
				break
			if n[i + 1] <= 0:
				n[i + 1] = n[i + 1] - n[i]
			if n[i] > 0 and n[i + 1] > 0:
				n.pop(i + 1)
			i += 1
		if pop_flag:
			i = 0
		else:
			i = -1
	return min(n)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	f = int(input())
	min_ele = min(arr)
	if f < min_ele:
		print('impossible')
	else:
		l = n - 1
		pow = int(math.log(l, 2))
		pow = 2 ** pow
		ind = (l - pow) * 2 + 1
		if f >= arr[ind - 1]:
			print('possible')
			print(ind, f)
		else:
			count = []
			for i in range(len(arr)):
				if f >= arr[i]:
					count.append(i)
			minimum = int('9' * 20)
			pos = -1
			for i in count:
				ans = validate(arr.copy(), i) * -1
				if minimum > ans:
					minimum = ans
					pos = i
			print('possible')
			print(pos + 1, minimum + f)


a = []

def fun(n, p, ans):
	d = 0
	ap1f = 0
	ap1l = p - 1
	ap1len = p
	ap2l = n - 1
	ap2len = n - p
	apcd = 1
	flag = True
	if ans == -1:
		flag = False
	while not (ap1len == 0 and ap2len == 1):
		if not (ap2len > 2 and ap1len == 0):
			if ap1len % 2 == 0:
				ap1l -= apcd
				ap1len = ap1len // 2
			else:
				d += a[ap1l]
				if flag and d > ans:
					return d
				ap1len = (ap1len + 1) // 2
			if ap2len % 2 == 0:
				ap2l -= apcd
				apcd *= 2
				ap2len = ap2len // 2
			else:
				apcd *= 2
				ap1f += apcd
				ap1len -= 1
				ap2len = (ap2len + 1) // 2
		elif ap2len % 2 == 0:
			ap2l -= apcd
			apcd *= 2
			ap2len = ap2len // 2
		else:
			d += a[ap2l]
			if flag and d > ans:
				return d
			apcd *= 2
			ap2len = (ap2len + 1) // 2
	return d

def mainfun(n, f):
	ans = -1
	p = -1
	for i in range(n):
		if a[i] <= f:
			temp = fun(n, i, ans)
			if ans == -1 or temp < ans:
				ans = temp
				p = i
	print('%d %d' % (p + 1, ans + f))
t = int(input())
for xxx in range(t):
	n = int(input())
	a = [int(c) for c in input().split()]
	f = int(input())
	flag = True
	for x in a:
		if x <= f:
			flag = False
			break
	if flag:
		print('impossible')
	else:
		print('possible')
		mainfun(n - 1, f)


def nothing():
	cx = 2
	if cx == 1:
		cx += 1
	elif cx == 0:
		cx += 1

def finals(a, nl, nr, ls, le, rs, re):
	f = True
	l1 = 0
	l2 = 0
	import math
	ans = 0
	while f == True:
		if nl + nr == 1:
			f = False
		else:
			if nl % 2 != 0:
				attx = int(le)
				ans = ans + a[attx]
				nl = (nl + 1) / 2
				l1 = l1 + 1
			elif nl % 2 == 0 and nl != 0:
				nl = nl / 2
				le = le - 2 ** l1
				l1 = l1 + 1
			if nr % 2 != 0:
				nr = (nr + 1) / 2
				if nl == 0:
					attx = int(re)
					ans = ans + a[attx]
					l2 = l2 + 1
				else:
					nl = nl - 1
					if nl != 0:
						ls = ls + 2 ** l2
					l2 = l2 + 1
			elif nr % 2 == 0:
				nr = nr / 2
				re = re - 2 ** l2
				l2 = l2 + 1
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	f = int(input())
	l1 = []
	for j in range(n - 1):
		if a[j] <= f:
			l1.append(j)
	ans = 0
	f1 = True
	save = 0
	pos = 0
	if len(l1) == 0:
		print('impossible')
	else:
		if len(l1) < 700000:
			for j in range(0, len(l1)):
				k = l1[j]
				if k == 0:
					h = finals(a, 0, n - 1, 0, 0, 0, n - 2)
				else:
					h = finals(a, k, n - 1 - k, 0, k - 1, k, n - 2)
				if ans == 0 and f1 == True:
					f1 = False
					ans = h
					save = k
				else:
					ans1 = min(h, ans)
					if ans1 != ans:
						ans = ans1
						save = k
		else:
			c1 = 0
			j = len(l1) - 1
			while c1 < 300000:
				k = l1[j]
				if k == 0:
					h = finals(a, 0, n - 1, 0, 0, 0, n - 2)
				else:
					h = finals(a, k, n - 1 - k, 0, k - 1, k, n - 2)
				if ans == 0 and f1 == True:
					f1 = False
					ans = h
					save = k
				else:
					ans1 = min(h, ans)
					if ans1 != ans:
						ans = ans1
						save = k
				j = j - 1
				c1 = c1 + 1
		nothing()
		ans = ans + f
		if save == 0:
			save = 1
		else:
			save = save + 1
		print('possible')
		print(save, ans)


from sys import stdin
from math import ceil

def func(arr):
	step = 0
	right = len(arr) - 1
	n = len(arr)
	while right != 1:
		step += 1
		if n % 2 != 0:
			right -= 2 ** (step - 1)
		else:
			arr[0] -= arr[right]
		n = ceil((n - 1) / 2) + 1
	return arr[0]
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	f = int(stdin.readline())
	indexes = [i for (i, x) in enumerate(arr) if x <= f]
	if len(indexes) == 0:
		print('impossible')
	else:
		print('possible')
		final = {}
		for ele in indexes:
			part = arr[0:ele]
			p = len(part)
			part = part[0:p:2]
			if p % 2 != 0:
				part.append(0 - part[-1])
			else:
				part.append(0)
			case = arr[ele:] + part
			ans = [case[-1]] + case[0:len(case) - 1]
			m = abs(func(ans))
			if m in final:
				final[m].append(ele)
			else:
				final[m] = [ele]
		print(min(final[min(list(final.keys()))]) + 1, min(list(final.keys())) + f)


import math
from copy import copy

def nextPowerOf2(n):
	n -= 1
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n += 1
	return n

def safepos(n):
	p = nextPowerOf2(n)
	m = (p - 1 - n) * 2
	ans = p - 1 - m
	return ans

def calcd(arr, i, f, n):
	arr.insert(i, f)
	aux = arr[:i:2]
	arr = arr[i:] + aux
	pos = n - i
	k = []
	if len(aux) > 0 and i % 2 != 0:
		arr[0] += aux[-1]
		k.append(aux[-1])
	while len(arr) > 2:
		if len(arr) % 2 == 0:
			arr[0] += arr[-1]
			k.append(arr[-1])
		arr = [arr[0]] + arr[1:n:2]
	return arr[0]
try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		f = int(input())
		pos = []
		for i in range(n - 1):
			if arr[i] <= f:
				pos.append(i)
		if len(pos) == 0:
			print('impossible')
			continue
		k = safepos(n - 1)
		if k - 1 in pos:
			print('possible')
			print(k, f)
		else:
			val = math.inf
			for i in pos:
				aux = copy(arr)
				temp = calcd(aux, i, f, n)
				if temp < val:
					val = temp
					posi = i + 1
			print('possible')
			print(posi, val)
except:
	pass


import math

def safeind(n):
	x = n
	n -= 1
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n += 1
	p = n
	m = (p - 1 - x) * 2
	ans = p - 1 - m
	return ans
try:
	t = int(input())
	for _ in range(t):
		N = int(input())
		n = list(map(int, input().split()))
		F = int(input())
		ind = []
		for i in range(N - 1):
			if n[i] <= F:
				ind.append(i)
		if len(ind) == 0:
			print('impossible')
			continue
		ans = safeind(N - 1) - 1
		if ans in ind:
			print('possible')
			print(ans + 1, F)
		else:
			D = math.inf
			for idx in ind:
				l = []
				for x in n:
					l.append(x)
				l.insert(idx, F)
				temp = l[:idx:2]
				l = l[idx:] + temp
				if len(temp) > 0 and idx % 2 != 0:
					l[0] += temp[-1]
				while len(l) > 2:
					if len(l) % 2 == 0:
						l[0] += l[-1]
					l = [l[0]] + l[1:N:2]
				d = l[0]
				if d < D:
					D = d
					pos = idx
			print('possible')
			print(pos + 1, D)
except:
	pass


from math import log

def fun(length, dic):
	if length in dic:
		return dic[length]
	else:
		dic[length] = []
		if length % 2 == 1:
			dic[length].append(length)
		arr = fun((length + 1) // 2, dic)
		for i in arr:
			dic[length].append(2 * i - 1)
		return dic[length]
dic = {}
dic[1] = []
dic[2] = []
t = int(input())
for hulala in range(t):
	n = int(input()) - 1
	arr = list(map(int, input().split()))
	f = int(input())
	last = []
	for i in range(n):
		if arr[i] <= f:
			last.append(i)
	if len(last) == 0:
		print('impossible')
	else:
		print('possible')
		check = 1
		if n > 750:
			x = n - 2 ** int(log(n, 2))
			if 2 * x == n - 1:
				temp = [2 * x]
			else:
				temp = [2 * x, 2 * x + 1]
			for j in temp:
				if arr[j] <= f:
					print(j + 1, f)
					check = 0
					break
		if check == 1:
			d = -1
			p = -1
			for i in last:
				ans = 0
				if i % 2 == 1:
					ans += arr[i - 1]
				surviving = arr[i:] + arr[:i:2]
				brr = fun(len(surviving), dic)
				for j in brr:
					ans += surviving[j - 1]
					if d != -1 and d < ans:
						break
				if d == -1 or ans < d:
					d = ans
					p = i
				if d == 0:
					break
			print(p + 1, d + f)


import math

def nextPowerOf2(n):
	n -= 1
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n += 1
	return n

def safepos(n):
	p = nextPowerOf2(n)
	m = (p - 1 - n) * 2
	ans = p - 1 - m
	return ans

def calculate(l, N):
	size = len(l)
	while size > 2:
		if size % 2 == 0:
			l[0] = l[0] + l[-1]
		aux = l[1:N:2]
		aux2 = [l[0]]
		l = aux2 + aux
		size = len(l)
	return l[0]
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	f = int(input())
	x = []
	for i in range(len(l)):
		x.append(i)
	sf = list(filter(lambda y: l[y] <= f, x))
	sflen = len(sf)
	if sflen == 0:
		print('impossible')
	else:
		anw = safepos(n - 1)
		anw = anw - 1
		if anw in sf:
			print('possible')
			print(anw + 1, f)
		else:
			mxd = math.inf
			for dd in range(0, len(sf)):
				templ = l[:]
				templ.insert(sf[dd], f)
				t1 = []
				t2 = []
				for zz in range(0, sf[dd], 2):
					t1.append(templ[zz])
				for ee in range(sf[dd], len(templ)):
					t2.append(templ[ee])
				templ = t2 + t1
				if len(t1) > 0:
					if sf[dd] % 2 != 0:
						templ[0] = templ[0] + t1[-1]
				fans = calculate(templ, n)
				if fans < mxd:
					mxd = fans
					pos = sf[dd]
			print('possible')
			print(pos + 1, mxd)