You are given an array $a$ consisting of $n$ integers. You can perform the following operations with it:   Choose some positions $i$ and $j$ ($1 \le i, j \le n, i \ne j$), write the value of $a_i \cdot a_j$ into the $j$-th cell and remove the number from the $i$-th cell;  Choose some position $i$ and remove the number from the $i$-th cell (this operation can be performed no more than once and at any point of time, not necessarily in the beginning). 

The number of elements decreases by one after each operation. However, the indexing of positions stays the same. Deleted numbers can't be used in the later operations.

Your task is to perform exactly $n - 1$ operations with the array in such a way that the only number that remains in the array is maximum possible. This number can be rather large, so instead of printing it you need to print any sequence of operations which leads to this maximum number. Read the output format to understand what exactly you need to print.


-----Input-----

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

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$) — the elements of the array.


-----Output-----

Print $n - 1$ lines. The $k$-th line should contain one of the two possible operations.

The operation of the first type should look like this: $1~ i_k~ j_k$, where $1$ is the type of operation, $i_k$ and $j_k$ are the positions of the chosen elements.

The operation of the second type should look like this: $2~ i_k$, where $2$ is the type of operation, $i_k$ is the position of the chosen element. Note that there should be no more than one such operation.

If there are multiple possible sequences of operations leading to the maximum number — print any of them.


-----Examples-----
Input
5
5 -2 0 1 -3

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

Input
5
5 2 0 4 0

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

Input
2
2 -1

Output
2 2

Input
4
0 -10 0 0

Output
1 1 2
1 2 3
1 3 4

Input
4
0 0 0 0

Output
1 1 2
1 2 3
1 3 4



-----Note-----

Let X be the removed number in the array. Let's take a look at all the examples:

The first example has, for example, the following sequence of transformations of the array: $[5, -2, 0, 1, -3] \to [5, -2, X, 1, -3] \to [X, -10, X, 1, -3] \to$ $[X, X, X, -10, -3] \to [X, X, X, X, 30]$. Thus, the maximum answer is $30$. Note, that other sequences that lead to the answer $30$ are also correct.

The second example has, for example, the following sequence of transformations of the array: $[5, 2, 0, 4, 0] \to [5, 2, X, 4, 0] \to [5, 2, X, 4, X] \to [X, 10, X, 4, X] \to$ $[X, X, X, 40, X]$. The following answer is also allowed: 

1 5 3

1 4 2

1 2 1

2 3



Then the sequence of transformations of the array will look like this: $[5, 2, 0, 4, 0] \to [5, 2, 0, 4, X] \to [5, 8, 0, X, X] \to [40, X, 0, X, X] \to$ $[40, X, X, X, X]$.

The third example can have the following sequence of transformations of the array: $[2, -1] \to [2, X]$.

The fourth example can have the following sequence of transformations of the array: $[0, -10, 0, 0] \to [X, 0, 0, 0] \to [X, X, 0, 0] \to [X, X, X, 0]$.

The fifth example can have the following sequence of transformations of the array: $[0, 0, 0, 0] \to [X, 0, 0, 0] \to [X, X, 0, 0] \to [X, X, X, 0]$.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))

cnt_zero, cnt_nega, cnt_nega_max, cnt_nega_max_pos = 0, 0, -1e10, -1
used = [0]*n

for i, v in enumerate(a):
    if v == 0:
        cnt_zero += 1
        used[i] = 1
        continue
    if v < 0:
        cnt_nega += 1
        if cnt_nega_max_pos == -1 or cnt_nega_max < v:
           cnt_nega_max = v
           cnt_nega_max_pos = i
if cnt_nega%2 == 1:
    used[cnt_nega_max_pos] = 1

if cnt_zero == n or (cnt_zero == n-1 and cnt_nega == 1):
    for i in range(n-1):
        print('1', i+1, i+2)
else:     
    left = -1
    for i in range(n):
        if used[i] == 1:
            if left != -1: print('1', left+1, i+1)
            left = i
    if left != -1:
        print('2', left+1)
    left = -1
    for i in range(n):
        if used[i] == 0:
            if left != -1: print('1', left+1, i+1)
            left = i


def main():
    n = int(input())
    a = list(map(int, input().split()))

    cnt_z, cnt_n, idx = 0, 0, -1
    z_idx = []
    a.append(-10**9-1)
    for i in range(n):
        if a[i] < 0:
            cnt_n += 1
            idx = i if a[idx] < a[i] else idx
        elif not a[i]:
            cnt_z += 1
            z_idx.append(i)

    if cnt_z == n or cnt_z == n - 1 and cnt_n == 1:
        for i in range(n-1):
            print(1, i+1, i+2)
        return

    used = [0 for i in range(n)]
    for i in range(cnt_z-1):
        print(1, z_idx[i]+1, z_idx[i+1]+1)
        used[z_idx[i]] = 1

    if cnt_n % 2 and cnt_z:
        print(1, idx+1, z_idx[-1]+1)
        used[idx] = 1
    elif cnt_n % 2:
        z_idx.append(idx)

    if len(z_idx):
        print(2, z_idx[-1]+1)
        used[z_idx[-1]] = 1

    lst = -1
    for i in range(n):
        if not used[i]:
            if lst != -1:
                print(1, lst+1, i+1)

            lst = i


def __starting_point():
    main()

__starting_point()

from enum import Enum

class OperationType(Enum):
	Multiply = 1
	Remove = 2

class RemoveOperation:
	def __init__(self, index):
		self.type = OperationType.Remove
		self.index = index

	def __repr__(self):
		return "RemoveOperation({})".format(self.index)

class MultiplyOperation:
	def __init__(self, index_a, index_b):
		self.type = OperationType.Multiply
		self.index_a = index_a
		self.index_b = index_b

	def __repr__(self):
		return "MultiplyOperation({}, {})".format(self.index_a, self.index_b)

def multiply_remaining(removed, n):
	"""
	Removed should be list of 1-based indices
	"""
	operations = []
	keep_indices = set(range(1, n + 1)) - set(removed)
	previous = None
	for index in sorted(keep_indices):
		if previous is not None:
			operations.append(MultiplyOperation(previous, index))
		previous = index
	return operations

def multiply_everything(n):
	operations = []
	for i in range(1, n):
		operations.append(MultiplyOperation(i, i + 1))
	return operations

def remove_indices_and_multiply_remaining(removed, n):
	"""
	Removed should be a collection of 1-based indices
	"""
	operations = []
	keep_indices = set(range(1, n + 1)) - set(removed)
	previous = None
	for index in sorted(keep_indices):
		if previous is not None:
			operations.append(MultiplyOperation(previous, index))
		previous = index
	return operations

def find_zero_indices(xs):
	"""
	Returns sorted list of 1-based indices
	"""
	zero_indices = []
	for index, x, in enumerate(xs):
		if x == 0:
			zero_indices.append(index + 1)
	return zero_indices

def remove_indices_and_multiply_remaining(indices_to_remove, n):
	"""
	indices_to_remove should be a sorted list of 1-based indices
	"""
	# multiply together indices to remove and then actually remove last one
	operations = []
	previous = None
	for index in indices_to_remove:
		if previous is not None:
			operations.append(MultiplyOperation(previous, index))
		previous = index
	
	if len(indices_to_remove) < n:
		operations.append(RemoveOperation(previous))
		operations += multiply_remaining(indices_to_remove, n)
	return operations

def find_index_of_largest_negative(xs):
	# or index of smallest absolute value negative
	# returns 1 based index
	maximum = float('-inf')
	maximum_index = None
	for index, x in enumerate(xs):
		if x < 0 and x > maximum:
			maximum = x
			maximum_index = index
	return maximum_index + 1

def solve(xs):
	"""
	Returns list of |xs| - 1 operations
	"""
	n = len(xs)
	# Count negatives and zeros
	negatives = 0
	zeros = 0
	for x in xs:
		if x == 0:
			zeros += 1
		if x < 0:
			negatives += 1
	
	if zeros == 0 and negatives == 0:
		# all positive so just multiply everything to maximize
		return multiply_everything(n)
	elif zeros == n:
		# can only be left with 0, multiply everything...
		return multiply_everything(n)
	elif zeros == 0 and negatives > 0:
		if negatives % 2 == 0:
			# multiply everything for largest positive number
			return multiply_everything(n)
		else:
			# get rid of smallest absolute value negative to be left with even number of negatives
			# then multiply everything for largest positive number
			return remove_indices_and_multiply_remaining([find_index_of_largest_negative(xs)], n)
	elif negatives == 0 and zeros > 0:
		return remove_indices_and_multiply_remaining(find_zero_indices(xs), n)
	else:#if zeros > 0 and negatives > 0
		if negatives % 2 == 0:
			# get rid of zeros and
			# multiply everything for largest positive number
			return remove_indices_and_multiply_remaining(find_zero_indices(xs), n)
		else:
			# get rid of zeros as well as smallest negative number
			# then multiply everything for largest positive number
			indices_to_remove = sorted([find_index_of_largest_negative(xs)] + find_zero_indices(xs))
			return remove_indices_and_multiply_remaining(indices_to_remove, n)

def verify(xs, maximum):
	solution = solve(xs)
	#print("solve(", xs, ") returned ", solution)

	assert len(solution) == len(xs) - 1

	num_removes = 0
	removed = [False] * len(xs)
	for operation in solution:
		if operation.type is OperationType.Remove:
			assert not removed[operation.index - 1]
			num_removes += 1
			removed[operation.index - 1] = True
		elif operation.type is OperationType.Multiply:
			assert not removed[operation.index_a - 1]
			assert not removed[operation.index_b - 1]
			removed[operation.index_a - 1] = True
			xs[operation.index_b - 1] *= xs[operation.index_a - 1]

	assert num_removes <= 1

	num_remaining = 0
	remaining_index = -1
	for index, value in enumerate(xs):
		if not removed[index]:
			num_remaining += 1
			remaining_index = index
		
	assert num_remaining == 1
	assert maximum == xs[remaining_index]

n = int(input())
xs = list(map(int, input().split()))[:n]
for operation in solve(xs):
	if operation.type is OperationType.Multiply:
		print(1, operation.index_a, operation.index_b)
	else:
		print(2, operation.index)

# verify([-1, -1, -1, -1, -1, -1], 1)
# verify([-1, -1, -1, -1, -1], 1)
# verify([-1, -1, -100, -1, -1], 100)
# verify([-100, -1, -1, -1, -1], 100)
# verify([0, 0], 0)
# verify([0, 0, 0], 0)
# verify([1, 2, 3], 6)
# verify([0, 2, 3], 6)
# verify([2, 0, 3], 6)
# verify([2, 1, 0, 3], 6)
# verify([2, 2, 0, 3], 12)
# verify([2, 2, 0, 0, 3], 12)
# verify([2, 2, 0, 0, 0, 3], 12)
# verify([0, 2, 2, 0, 0, 0, 3], 12)
# verify([2, 2, 0, 0, 0, 3], 12)
# verify([0, 2, 0, 2, 0, 0, 0, 3, 0], 12)
# verify([-1, 2, 3], 6)
# verify([2, -1, 3], 6)
# verify([2, 3, -100], 6)
# verify([2, 0, 3, -1, -100], 600)
# verify([2, 0, -1, -100, 3, -2, -2], 2400)
# verify([2, 0, -1, -100, 3, -2, -2, 0], 2400)
# verify([2, 0, -1, -100, 3, -2, -2, 0, 2], 4800)
# verify([0, -1, 5], 5)
# verify([0, -1, 0, 5], 5)
# verify([0, -1, 0, -100, 5], 500)
# verify([0, -2, 0, -100, -5, 5], 2500)
# verify([0, -10, 0, 0], 0)
# verify([0, -10, -10, 0], 100)


n=int(input())
a=[int(el) for el in input().split()]
k0=0
kotr=0
index_minotr=0
minotr=float('-inf')
minotr_index=-1
minabs=float('+inf')
minabs_index=-1
index0=-1
for i in range (n):
    if a[i]==0:
        k0+=1
        index0=i
    else:
        if abs(a[i])<minabs:
            minabs=abs(a[i])
            minabs_index=i
    if a[i]<0:
        kotr+=1
        if a[i]>minotr:
            minotr=a[i]
            minotr_index=i



if k0==n-1 and kotr==0:
    for i in range (n-1):
        for j in range (i+1,n):
            if a[i]==0 and a[j]==0:
                print(1,i+1,j+1)
                index0=j
#                a[i]=1
                break
    print(2, index0+1)
    raise SystemExit()

if (k0==n-1 and kotr==1) or k0==n:
    i=0
    for i in range(n-1):
        print(1,i+1,i+2)
    raise SystemExit



if kotr%2==0:
    for i in range(n-1):
        for j in range(i+1,n):
            if a[i]==0 and a[j]==0:
                print(1,i+1,j+1)
                index0=max(index0,j)
                break
            if a[i]!=0 and a[j]!=0:
                print(1,i+1,j+1)
                break
    if index0!=-1:
        print(2,index0+1)
    raise SystemExit

#кол-во отрицательных нечетно
#перемножаем все нули с минимальным нечетным и удаляем


for i in range(n-1):

    for j in range(i+1,n):

        if a[i]==0 and a[j]==0:
            print(1,i+1,j+1)
            index0=max(index0,j)
            break
        if a[i]==0 and j==minotr_index:
            print(1,i+1,j+1)
            index0=max(index0,j)
            a[j]=0
            break
        if i==minotr_index and a[j]==0:
            print(1,i+1,j+1)
            index0=max(index0,j)

            break
        if i!=minotr_index and j!=minotr_index and a[i]*a[j]!=0:
            print(1,i+1,j+1)
            break


if index0==-1:
    print(2,minotr_index+1)
else:
    print(2,index0+1)





n = int(input())

a = list(map(int,input().split()))

ct = 0
mn = 1000000000000000000
pos = 0
is_all_zero = True

for i in range(n):
    x = a[i]
    if x < 0:
        ct += 1
        if mn > abs(x):
            mn = abs(x)
            pos = i



if ct%2 == 1:
    a[pos] = 0

for x in a:
    if x != 0:
        is_all_zero = False
        

if is_all_zero:
    for i in range(n-1):
        print(1,i+1,i+2)
    return


pre = 0
pre0 = 0

for i in range(n):
    if a[i] == 0:
        if pre0:
            print(1,pre0,i+1)
        pre0 = i+1
    else:
        if pre == 0:
            pre = i+1
        else:
            print(1,pre,i+1)
            pre = i+1

if pre0:
    print(2,pre0)