Yet another round on DecoForces is coming! Grandpa Maks wanted to participate in it but someone has stolen his precious sofa! And how can one perform well with such a major loss?

Fortunately, the thief had left a note for Grandpa Maks. This note got Maks to the sofa storehouse. Still he had no idea which sofa belongs to him as they all looked the same!

The storehouse is represented as matrix n × m. Every sofa takes two neighbouring by some side cells. No cell is covered by more than one sofa. There can be empty cells.

Sofa A is standing to the left of sofa B if there exist two such cells a and b that x_{a} < x_{b}, a is covered by A and b is covered by B. Sofa A is standing to the top of sofa B if there exist two such cells a and b that y_{a} < y_{b}, a is covered by A and b is covered by B. Right and bottom conditions are declared the same way. 

Note that in all conditions A ≠ B. Also some sofa A can be both to the top of another sofa B and to the bottom of it. The same is for left and right conditions.

The note also stated that there are cnt_{l} sofas to the left of Grandpa Maks's sofa, cnt_{r} — to the right, cnt_{t} — to the top and cnt_{b} — to the bottom.

Grandpa Maks asks you to help him to identify his sofa. It is guaranteed that there is no more than one sofa of given conditions.

Output the number of Grandpa Maks's sofa. If there is no such sofa that all the conditions are met for it then output -1.


-----Input-----

The first line contains one integer number d (1 ≤ d ≤ 10^5) — the number of sofas in the storehouse.

The second line contains two integer numbers n, m (1 ≤ n, m ≤ 10^5) — the size of the storehouse.

Next d lines contains four integer numbers x_1, y_1, x_2, y_2 (1 ≤ x_1, x_2 ≤ n, 1 ≤ y_1, y_2 ≤ m) — coordinates of the i-th sofa. It is guaranteed that cells (x_1, y_1) and (x_2, y_2) have common side, (x_1, y_1)  ≠  (x_2, y_2) and no cell is covered by more than one sofa.

The last line contains four integer numbers cnt_{l}, cnt_{r}, cnt_{t}, cnt_{b} (0 ≤ cnt_{l}, cnt_{r}, cnt_{t}, cnt_{b} ≤ d - 1).


-----Output-----

Print the number of the sofa for which all the conditions are met. Sofas are numbered 1 through d as given in input. If there is no such sofa then print -1.


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

Output
1

Input
3
10 10
1 2 1 1
5 5 6 5
6 4 5 4
2 1 2 0

Output
2

Input
2
2 2
2 1 1 1
1 2 2 2
1 0 0 0

Output
-1



-----Note-----

Let's consider the second example.   The first sofa has 0 to its left, 2 sofas to its right ((1, 1) is to the left of both (5, 5) and (5, 4)), 0 to its top and 2 to its bottom (both 2nd and 3rd sofas are below).  The second sofa has cnt_{l} = 2, cnt_{r} = 1, cnt_{t} = 2 and cnt_{b} = 0.  The third sofa has cnt_{l} = 2, cnt_{r} = 1, cnt_{t} = 1 and cnt_{b} = 1. 

So the second one corresponds to the given conditions.

In the third example   The first sofa has cnt_{l} = 1, cnt_{r} = 1, cnt_{t} = 0 and cnt_{b} = 1.  The second sofa has cnt_{l} = 1, cnt_{r} = 1, cnt_{t} = 1 and cnt_{b} = 0. 

And there is no sofa with the set (1, 0, 0, 0) so the answer is -1.

Difficulty: interview

Starter code:

Solutions:
from sys import stdin, stdout

k = int(stdin.readline())
n, m = map(int, stdin.readline().split())
left, right, down, up = [], [], [], []
coordinates = []

for i in range(k):
    x1, y1, x2, y2 = map(int, stdin.readline().split())
    
    if x1 == x2:
        if y1 < y2:
            coordinates.append((x1, y1, x2, y2, i))
        else:
            coordinates.append((x2, y2, x1, y1, i))
    else:
        if x1 < x2:
            coordinates.append((x1, y1, x2, y2, i))
        else:
            coordinates.append((x2, y2, x1, y1, i))
    
    left.append(coordinates[-1])
    right.append(coordinates[-1])
    up.append(coordinates[-1])
    down.append(coordinates[-1])

left.sort(key = lambda x: (x[0], x[2]))
down.sort(key = lambda x: (x[1], x[3]))

challengers = [[], [], [], []]
cntl, cntr, cntd, cntu = map(int, stdin.readline().split())
label = 1

if cntl or not cntl:
    for i in range(cntl, -1, -1):
        if (left[i][0], left[i][2]) == (left[cntl][0], left[cntl][2]):
            challengers[0].append(left[i][-1])  
        else:
            break
        
    for i in range(cntl + 1, k):
        if (left[i][0], left[i][2]) == (left[cntl][0], left[cntl][2]) and left[i][2] > left[i][0]:
            label = 0
        
        if (left[i][0], left[i][2]) == (left[cntl][0], left[cntl][2]):
            challengers[0].append(left[i][-1])  
        else:
            break

if cntr or not cntr:
    for i in range(k - 1 - cntr, k):
        if (left[i][0], left[i][2]) == (left[k - 1 - cntr][0], left[k - 1 - cntr][2]):
            challengers[1].append(left[i][-1])
        else:
            break
    
    for i in range(k - 2 - cntr, -1, -1):
        if (left[i][0], left[i][2]) == (left[k - 1 - cntr][0], left[k - 1 - cntr][2]) and left[i][2] > left[i][0]:
            label = 0
        
        if (left[i][0], left[i][2]) == (left[k - 1 - cntr][0], left[k - 1 - cntr][2]):
            challengers[1].append(left[i][-1])
        else:
            break

#!!!!!!!!!!!

if cntd or not cntd:
    for i in range(cntd, -1, -1):
        if (down[i][1], down[i][3]) == (down[cntd][1], down[cntd][3]):
            challengers[2].append(down[i][-1])
        else:
            break
        
    for i in range(cntd + 1, k):
        if (down[i][1], down[i][3]) == (down[cntd][1], down[cntd][3]) and down[i][3] > down[i][1]:
            label = 0
            
        if (down[i][1], down[i][3]) == (down[cntd][1], down[cntd][3]):
            challengers[2].append(down[i][-1])  
        else:
            break
        
if cntu or not cntu:
    for i in range(k - 1 - cntu, k):
        if (down[i][1], down[i][3]) == (down[k - 1 - cntu][1], down[k - 1 - cntu][3]):
            challengers[3].append(down[i][-1])
        else:
            break
    
    for i in range(k - 2 - cntu, -1, -1):
        if (down[i][1], down[i][3]) == (down[k - 1 - cntu][1], down[k - 1 - cntu][3]) and down[i][3] > down[i][1]:
            label = 0
        
        if (down[i][1], down[i][3]) == (down[k - 1 - cntu][1], down[k - 1 - cntu][3]):
            challengers[3].append(down[i][-1])
        else:
            break

ans = set(challengers[0]) & set(challengers[1]) & set(challengers[2]) & set(challengers[3])

if not len(ans) or not label:
    stdout.write('-1')
else:
    stdout.write(str(list(ans)[0] + 1))

#!/usr/bin/env python3


d = int(input().strip())
[n, m] = list(map(int, input().strip().split()))
Hxds = [0 for _ in range(n)]
Hyds = [0 for _ in range(m)]
Vxds = [0 for _ in range(n)]
Vyds = [0 for _ in range(m)]
ds = []
for i in range(d):
	x1, y1, x2, y2 = list(map(int, input().strip().split()))
	if x1 == x2:
		Hxds[x1 - 1] += 1
		Hyds[min(y1, y2) - 1] += 1
		ds.append((x1 - 1, min(y1, y2) - 1, 'h'))
	else:
		Vxds[min(x1, x2) - 1] += 1
		Vyds[y1 - 1] += 1
		ds.append((min(x1, x2) - 1, y1 - 1, 'v'))
cl, cr, ct, cb = list(map(int, input().strip().split()))

if (d - 1 - cl - cr) * (d - 1 - ct - cb) > 0:
	print(-1)
	return


def makeI(xs):
	I = [0 for _ in range(len(xs) + 1)]
	for i in range(len(xs)):
		I[i + 1] = I[i] + xs[i]
	return I

def find_x_Hor(IH, IV, l, cl, cr):
	if cl + cr > d - 1:
		return -1
	x = 0
	while x <= l and (IH[x] + IV[x] < cl or d - IH[x + 1] - IV[x] > cr):
		x += 1
	if x < l and IH[x] + IV[x] == cl and (d - IH[x + 1] - IV[x]) == cr:
		return x
	return -1

def find_x_Vert(IH, IV, l, cl, cr):
	if cl + cr < d - 1:
		return -1
	x = 0
	while x < l and (IH[x + 1] + IV[x + 1] < cl + 1 or d - IH[x + 1] - IV[x] > cr + 1):
		x += 1
	if x < l and IH[x + 1] + IV[x + 1] == cl + 1 and (d - IH[x + 1] - IV[x]) == cr + 1:
		return x
	return -1
	

IHx = makeI(Hxds)
IHy = makeI(Hyds)
IVx = makeI(Vxds)
IVy = makeI(Vyds)

if ct + cb >= d - 1 and cr + cl <= d - 1:  # horizontal sofa
	x = find_x_Hor(IHx, IVx, n, cl, cr)
	y = find_x_Vert(IVy, IHy, m, ct, cb)
	if x >= 0 and y >= 0:
		if (x, y, 'h') in ds:
			print(ds.index((x, y, 'h')) + 1)
			return

if ct + cb <= d - 1 and cr + cl >= d - 1:  # vertical sofa
	x = find_x_Vert(IHx, IVx, n, cl, cr)
	y = find_x_Hor(IVy, IHy, m, ct, cb)
	if x >= 0 and y >= 0:
		if (x, y, 'v') in ds:
			print(ds.index((x, y, 'v')) + 1)
			return

print(-1)



from sys import stdin, stdout



k = int(stdin.readline())

n, m = list(map(int, stdin.readline().split()))

left, right, down, up = [], [], [], []

coordinates = []



for i in range(k):

    x1, y1, x2, y2 = list(map(int, stdin.readline().split()))

    

    if x1 == x2:

        if y1 < y2:

            coordinates.append((x1, y1, x2, y2, i))

        else:

            coordinates.append((x2, y2, x1, y1, i))

    else:

        if x1 < x2:

            coordinates.append((x1, y1, x2, y2, i))

        else:

            coordinates.append((x2, y2, x1, y1, i))

    

    left.append(coordinates[-1])

    right.append(coordinates[-1])

    up.append(coordinates[-1])

    down.append(coordinates[-1])



left.sort(key = lambda x: (x[0], x[2]))

down.sort(key = lambda x: (x[1], x[3]))



challengers = [[], [], [], []]

cntl, cntr, cntd, cntu = list(map(int, stdin.readline().split()))

label = 1



if cntl or not cntl:

    for i in range(cntl, -1, -1):

        if (left[i][0], left[i][2]) == (left[cntl][0], left[cntl][2]):

            challengers[0].append(left[i][-1])  

        else:

            break

        

    for i in range(cntl + 1, k):

        if (left[i][0], left[i][2]) == (left[cntl][0], left[cntl][2]) and left[i][2] > left[i][0]:

            label = 0

        

        if (left[i][0], left[i][2]) == (left[cntl][0], left[cntl][2]):

            challengers[0].append(left[i][-1])  

        else:

            break



if cntr or not cntr:

    for i in range(k - 1 - cntr, k):

        if (left[i][0], left[i][2]) == (left[k - 1 - cntr][0], left[k - 1 - cntr][2]):

            challengers[1].append(left[i][-1])

        else:

            break

    

    for i in range(k - 2 - cntr, -1, -1):

        if (left[i][0], left[i][2]) == (left[k - 1 - cntr][0], left[k - 1 - cntr][2]) and left[i][2] > left[i][0]:

            label = 0

        

        if (left[i][0], left[i][2]) == (left[k - 1 - cntr][0], left[k - 1 - cntr][2]):

            challengers[1].append(left[i][-1])

        else:

            break



#!!!!!!!!!!!



if cntd or not cntd:

    for i in range(cntd, -1, -1):

        if (down[i][1], down[i][3]) == (down[cntd][1], down[cntd][3]):

            challengers[2].append(down[i][-1])

        else:

            break

        

    for i in range(cntd + 1, k):

        if (down[i][1], down[i][3]) == (down[cntd][1], down[cntd][3]) and down[i][3] > down[i][1]:

            label = 0

            

        if (down[i][1], down[i][3]) == (down[cntd][1], down[cntd][3]):

            challengers[2].append(down[i][-1])  

        else:

            break

        

if cntu or not cntu:

    for i in range(k - 1 - cntu, k):

        if (down[i][1], down[i][3]) == (down[k - 1 - cntu][1], down[k - 1 - cntu][3]):

            challengers[3].append(down[i][-1])

        else:

            break

    

    for i in range(k - 2 - cntu, -1, -1):

        if (down[i][1], down[i][3]) == (down[k - 1 - cntu][1], down[k - 1 - cntu][3]) and down[i][3] > down[i][1]:

            label = 0

        

        if (down[i][1], down[i][3]) == (down[k - 1 - cntu][1], down[k - 1 - cntu][3]):

            challengers[3].append(down[i][-1])

        else:

            break



ans = set(challengers[0]) & set(challengers[1]) & set(challengers[2]) & set(challengers[3])



if not len(ans) or not label:

    stdout.write('-1')

else:

    stdout.write(str(list(ans)[0] + 1))



# Made By Mostafa_Khaled


import sys
try:
    fin=open('in')
except:
    fin=sys.stdin
input=fin.readline

d = int(input())
n, m = map(int, input().split())
x1, y1, x2, y2 = [], [], [], []
T=[]
for _ in range(d):
    u, v, w, x = map(int, input().split())
    if u>w:u,w=w,u
    if v>x:v,x=x,v
    x1.append(u)
    y1.append(v)
    x2.append(-w)#the other direction pog?
    y2.append(-x)
    T.append([u,v,w,x])

x1.sort()
x2.sort()
y1.sort()
y2.sort()

req=list(map(int,input().split())) # x1,x2,y1,y2
import bisect
for i in range(len(T)):
    # binary search
    u,v,w,x=T[i]
    if req[0]==bisect.bisect_left(x1,w)-(u!=w):
        if req[1]==bisect.bisect_left(x2,-u)-(u!=w):
            if req[2]==bisect.bisect_left(y1,x)-(v!=x):
                if req[3]==bisect.bisect_left(y2,-v)-(v!=x):
                    print(i+1)
                    break
else:
    print(-1)