You are given an axis-aligned rectangle in a 2D Cartesian plane. The bottom left corner of this rectangle has coordinates (0,0)$(0, 0)$ and the top right corner has coordinates (N−1,N−1)$(N-1, N-1)$. You are also given K$K$ light sources; each light source is a point inside or on the perimeter of the rectangle.
For each light source, let's divide the plane into four quadrants by a horizontal and a vertical line passing through this light source. The light source can only illuminate one of these quadrants (including its border, i.e. the point containing the light source and two half-lines), but the quadrants illuminated by different light sources may be different.
You want to assign a quadrant to each light source in such a way that when they illuminate their respective quadrants, the entire rectangle (including its perimeter) is illuminated. Find out whether it is possible to assign quadrants to light sources in such a way.

-----Input-----
- The first line of the input contains an integer T$T$ denoting the number of test cases. The description of the test cases follows.
- The first line of each test case contains two space-separated integers K$K$ and N$N$.
- Each of the next K$K$ lines contains two space-separated integers x$x$ and y$y$ denoting a light source with coordinates (x,y)$(x, y)$.

-----Output-----
For each test case, print a single line containing the string "yes" if it is possible to illuminate the whole rectangle or "no" if it is impossible.

-----Constraints-----
- 1≤T≤5,000$1 \le T \le 5,000$
- 1≤K≤100$1 \le K \le 100$
- 1≤N≤109$1 \le N \le 10^9$
- 0≤x,y≤N−1$0 \le x, y \le N-1$
- no two light sources coincide

-----Example Input-----
2
2 10
0 0
1 0
2 10
1 2
1 1

-----Example Output-----
yes
no

Difficulty: interview

Starter code:

Solutions:
# https://www.codechef.com/problems/RECTLIT

def assess(sq,points):
    EWct = 0
    NSct = 0
    for a,b in points:
        EW = (a == 0 or a == sq)
        NS = (b == 0 or b == sq)
        if EW and NS:
            return 'yes'
        EWct += EW
        NSct += NS
    if NSct + EWct == 0 or len(points) == 1:
        return 'no'
    if EWct >= 2 or NSct >= 2:
        return 'yes'
    if len(points) == 2:
        return 'no'
    # now 3 points
    if NSct == 1 and EWct == 1:
        return 'yes'
    # 3 points, one on edge
    x = -1
    for a,b in points:
        if EWct > 0:
            if a == 0 or a == sq:
                e = b
            elif x == -1:
                x = b
            else:
                y = b
        else:
            if b == 0 or b == sq:
                e = a
            elif x == -1:
                x = a
            else:
                y = a
    if (e-x)*(e-y) < 0: # edge splits mids
        return 'no'
    else:
        return 'yes'


for ti in range(int(input())):
    k,n = map(int, input().split())
    if k > 3:
        for ki in range(k):
            input()
        print('yes')
    else:
        pos = [tuple(map(int, input().split())) for ki in range(k)]
        print(assess(n-1,pos))



t=int(input())
while t:
    k,n=map(int,input().split())
    l=[]
    j=0
    h=k
    while h:
        p=list(map(int,input().split()))
        l.append(p)
        h-=1
    if k>3:
        j=1
    elif k==1:
        if (l[0][0]==0 and l[0][1]==n-1) or (l[0][0]==0 and l[0][1]==0) or (l[0][0]==n-1 and l[0][1]==0) or (l[0][0]==n-1 and l[0][1]==n-1):
            j=1
    elif k==2:
        for q in range(2):
            if (l[q][0]==0 and l[q][1]==n-1) or (l[q][0]==0 and l[q][1]==0) or (l[q][0]==n-1 and l[q][1]==0) or (l[q][0]==n-1 and l[q][1]==n-1):
                j=1
        if l[0][0]==0 or l[0][0]==n-1:
            if l[1][0]==0 or l[1][0]==n-1: 
                j=1
        if l[0][1]==0 or l[0][1]==n-1:
            if l[1][1]==0 or l[1][1]==n-1: 
                j=1
    elif k==3:
        for q in range(3):
            if (l[q][0]==0 and l[q][1]==n-1) or (l[q][0]==0 and l[q][1]==0) or (l[q][0]==n-1 and l[q][1]==0) or (l[q][0]==n-1 and l[q][1]==n-1):
                j=1
        for q in range(2):
            for w in range(q+1,3):
                if l[q][0]==0 or l[q][0]==n-1:
                    if l[w][0]==0 or l[w][0]==n-1: 
                        j=1
                if l[q][1]==0 or l[q][1]==n-1:
                    if l[w][1]==0 or l[w][1]==n-1:
                        j=1
                if l[q][0]==0 or l[q][0]==n-1:
                    if l[w][1]==0 or l[w][1]==n-1:
                        j=1
                if l[q][1]==0 or l[q][1]==n-1:
                    if l[w][0]==0 or l[w][0]==n-1:
                        j=1
        for q in range(3):
            w=(q+1)%3
            r=(q+2)%3
            if l[q][0]==0 or l[q][0]==n-1:
                if (l[q][1]-l[w][1])*(l[q][1]-l[r][1])>=0:
                    j=1
            if l[q][1]==0 or l[q][1]==n-1:
                if (l[q][0]-l[w][0])*(l[q][0]-l[r][0])>=0:
                    j=1
    if j:
        print("yes")
    else:
        print("no")
    t-=1