1354G - Find a Gift - CodeForces Solution

import random
import sys, os
input = sys.stdin.buffer.readline

t = int(input())
u, v = "?".encode(), "!".encode()
for _ in range(t):
    n, k = map(int, input().split())
    if n <= 50:
        mi = 50
        ans = 0
        for x in range(2, n + 1):
            os.write(1, b"%s %d %d\n%d\n%d\n" % (u, 1, 1, 1, x))
            s = input().rstrip().decode()
            if s == "SECOND":
                ans = 1
                break
            elif s == "FIRST":
                mi = min(mi, x)
        if not ans:
            ans = mi
        os.write(1, b"%s %d\n" % (v, ans))
        continue
    ok = 0
    for _ in range(28):
        x = random.randint(2, n)
        os.write(1, b"%s %d %d\n%d\n%d\n" % (u, 1, 1, 1, x))
        s = input().rstrip().decode()
        if s == "SECOND":
            os.write(1, b"%s %d\n" % (v, 1))
            ok = 1
            break
    if ok:
        continue
    d = 1
    while True:
        if 2 * d + 1 > n:
            l, r = d + 1, n + 1
            break
        ka, kb = d, d
        a = " ".join(map(str, [i for i in range(1, d + 1)])).encode()
        b = " ".join(map(str, [i for i in range(d + 1, 2 * d + 1)])).encode()
        os.write(1, b"%s %d %d\n%s\n%s\n" % (u, ka, kb, a, b))
        s = input().rstrip().decode()
        if s == "FIRST":
            l, r = d + 1, 2 * d + 1
            break
        d *= 2
    while abs(l - r) > 1:
        m = (l + r) // 2
        d = m - l
        ka, kb = d, d
        a = " ".join(map(str, [i for i in range(1, d + 1)])).encode()
        b = " ".join(map(str, [i for i in range(l, m)])).encode()
        os.write(1, b"%s %d %d\n%s\n%s\n" % (u, ka, kb, a, b))
        s = input().rstrip().decode()
        if s == "FIRST":
            r = m
        else:
            l = m
    ans = l
    os.write(1, b"%s %d\n" % (v, ans))
exit()