L4-M1 - Questions & Answers

n = int(input())
k = {}

for i in range(n):
    inp = input().split()
    if inp[1] not in k:
        k[inp[1]] = []
    k[inp[1]].append(inp[0])

p = input()
t = k[p]
print(len(k[t[0]]))

t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    
    # dp table
    dp = [[0]*n for _ in range(n)]
    
    # precompute max for all subarrays
    max_arr = [[0]*n for _ in range(n)]
    for i in range(n):
        max_arr[i][i] = arr[i]
        for j in range(i+1, n):
            max_arr[i][j] = max(max_arr[i][j-1], arr[j])
    
    # fill dp
    for length in range(1, n+1):
        for l in range(n - length + 1):
            r = l + length - 1
            
            turn = n - (r - l)
            
            if l == r:
                dp[l][r] = arr[l]*turn + arr[l]
            else:
                left = arr[l]*turn + max_arr[l][r] + dp[l+1][r]
                right = arr[r]*turn + max_arr[l][r] + dp[l][r-1]
                dp[l][r] = max(left, right)
    
    print(dp[0][n-1])

import sys

def evolve_once(s_chars, ones_indices):
    n = len(s_chars)
    nxt = ['0'] * n
    for i in ones_indices:
        if i - 1 >= 0 and s_chars[i-1] == '0':
            nxt[i-1] = '1'
        if i + 1 < n and s_chars[i+1] == '0':
            nxt[i+1] = '1'
    return nxt

def final_after_k(s, K):
    if K == 0:
        return s
    n = len(s)
    s_chars = list(s)
    ones = {i for i,ch in enumerate(s_chars) if ch == '1'}
    if not ones:
        return '0' * n
    seen = {}
    t = 0
    cur_key = ''.join(s_chars)
    seen[cur_key] = 0
    while t < K:
        nxt_chars = evolve_once(s_chars, ones)
        t += 1
        nxt_key = ''.join(nxt_chars)
        if nxt_key in seen:
            start = seen[nxt_key]
            cycle_len = t - start
            rem = (K - t) % cycle_len
            s_cur = nxt_chars
            ones_cur = {i for i,ch in enumerate(s_cur) if ch == '1'}
            for _ in range(rem):
                s_cur = evolve_once(s_cur, ones_cur)
                ones_cur = {i for i,ch in enumerate(s_cur) if ch == '1'}
            return ''.join(s_cur)
        seen[nxt_key] = t
        s_chars = nxt_chars
        ones = {i for i,ch in enumerate(s_chars) if ch == '1'}
        if not ones:
            return ''.join(s_chars)
    return ''.join(s_chars)

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    T = int(next(it))
    out_lines = []
    for _ in range(T):
        N = int(next(it))
        K = int(next(it))
        S = next(it).strip()
        out_lines.append(final_after_k(S, K))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

n = int(input().strip())
t = int(input().strip())
s = list(input().strip())

for _ in range(t):
    i = 0
    while i < n - 1:
        if s[i] == 'B' and s[i + 1] == 'G':
            s[i], s[i + 1] = s[i + 1], s[i]
            i += 2  # skip next index to enforce simultaneous swaps
        else:
            i += 1

print("".join(s))

statement = input("Enter the C-style statement: ")

int_vars = []
char_vars = []

declarations = statement.split(';')

for decl in declarations:
    decl = decl.strip()
    if decl == '':
        continue
    
    if decl.startswith('int '):
        dtype = 'int'
        vars_part = decl[4:]  
    elif decl.startswith('char '):
        dtype = 'char'
        vars_part = decl[5:]  
    else:
        continue 
    vars_list = vars_part.split(',')
    
    for var in vars_list:
        var = var.strip()
        if var == '':
            continue
        
        if '=' in var:
            name, value = var.split('=', 1)
            name = name.strip()
            value = value.strip()
        else:
            name = var
            value = 'junk'
        
        if dtype == 'int':
            int_vars.append(f"{name}={value}")
        else:
            char_vars.append(f"{name}={value}")

if int_vars:
    print("Integers")
    for v in int_vars:
        print(v)

if char_vars:
    print("Characters")
    for v in char_vars:
        print(v)

text = input()
first = input()
second = input()

words = text.split()
result = []

for i in range(len(words) - 2):
    if words[i] == first and words[i + 1] == second:
        result.append(words[i + 2])

for word in result:
    print(word)

def soln(ingredients, n):
    ones = ingredients.count('1')
    twos = ingredients.count('2')
    threes = ingredients.count('3')
    
    if ones != twos or twos != threes or ones == 0:
        return 0
    
    if ones == 1 and twos == 1 and threes == 1:
        pos1 = ingredients.index('1')
        pos2 = ingredients.index('2')
        pos3 = ingredients.index('3')
        return 1 if pos1 < pos2 < pos3 else 0
    
    return 0

print(soln(input().strip(), int(input())))

from itertools import combinations

def min_menu_items(n, preferences):
customers = list(preferences.values())

for r in range(1, n + 1):
for combo in combinations(range(n), r):
if all(any(item in combo for item in customer) for customer in customers):
return len(combo), list(combo)
return -1, []

n = int(input())
t = int(input())
preferences = dict()
for i in range(0,t):
preferences[i] = eval(input())

count, items = min_menu_items(n, preferences)
print(count)

from collections import deque
import copy

def rotting_oranges(grid):
    """
    Calculates the minimum time required for all fresh oranges to become rotten in a grid.
    """
    if not grid or not grid[0]:
        return "All oranges can become rotten in 0 time frames."

    m = len(grid)
    n = len(grid[0])
    queue = deque()
    fresh_count = 0
    
    # Initialize the queue with rotten oranges and count fresh oranges
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 2:
                queue.append((i, j, 0))
            elif grid[i][j] == 1:
                fresh_count += 1
    
    # If there are no fresh oranges, time required is 0
    if fresh_count == 0:
        return "All oranges can become rotten in 0 time frames."
    
    # If there are fresh oranges but no rotten ones, it's impossible
    if not queue:
        return "All oranges cannot rot"
    
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    max_time = 0
    
    # Start BFS
    while queue:
        x, y, time = queue.popleft()
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # Check for valid and fresh neighbors
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                grid[nx][ny] = 2  # Rot the orange
                fresh_count -= 1
                max_time = max(max_time, time + 1)
                queue.append((nx, ny, time + 1))
    
    # Check if all fresh oranges were reached
    if fresh_count == 0:
        return f"All oranges can become rotten in {max_time} time frames."
    else:
        return "All oranges cannot rot"
m, n = map(int, input().split())
grid = []
for _ in range(m):
  row = list(map(int, input().split()))
  grid.append(row)

print(rotting_oranges(grid))

def rotate_matrix(matrix, m, n, r):
    layers = min(m, n) // 2
    
    for layer in range(layers):
        elements = []
        
        top = layer
        bottom = m - 1 - layer
        left = layer
        right = n - 1 - layer
        
        for j in range(left, right + 1):
            elements.append(matrix[top][j])
        
        for i in range(top + 1, bottom + 1):
            elements.append(matrix[i][right])
        
        if bottom > top:
            for j in range(right - 1, left - 1, -1):
                elements.append(matrix[bottom][j])
        
        if right > left:
            for i in range(bottom - 1, top, -1):
                elements.append(matrix[i][left])
        
        layer_size = len(elements)
        if layer_size == 0:
            continue
            
        rotations = r % layer_size
        elements = elements[rotations:] + elements[:rotations]
        
        idx = 0
        
        for j in range(left, right + 1):
            matrix[top][j] = elements[idx]
            idx += 1
        
        for i in range(top + 1, bottom + 1):
            matrix[i][right] = elements[idx]
            idx += 1
        
        if bottom > top:
            for j in range(right - 1, left - 1, -1):
                matrix[bottom][j] = elements[idx]
                idx += 1
        
        if right > left:
            for i in range(bottom - 1, top, -1):
                matrix[i][left] = elements[idx]
                idx += 1
    
    return matrix

m, n, r = map(int, input().split())
matrix = []
for _ in range(m):
    row = list(map(int, input().split()))
    matrix.append(row)

rotated_matrix = rotate_matrix(matrix, m, n, r)

for row in rotated_matrix:
    print(' '.join(map(str, row)))

def mod_eleven(num_str):
    odd_sum = 0
    even_sum = 0
    
    for i, digit in enumerate(reversed(num_str)):
        if i % 2 == 0:
            odd_sum += int(digit)
        else:
            even_sum += int(digit)
    
    return (odd_sum - even_sum) % 11

num_str = input().strip()
print(mod_eleven(num_str))

def max_money(n, amounts, deadlines):
    jobs = list(zip(amounts, deadlines))
    jobs.sort(key=lambda x: x[0], reverse=True)
    
    max_deadline = max(deadlines)
    schedule = [False] * (max_deadline + 1)
    total_money = 0
    
    for amount, deadline in jobs:
        for time in range(min(deadline, max_deadline), 0, -1):
            if not schedule[time]:
                schedule[time] = True
                total_money += amount
                break
    
    return total_money

n = int(input())
amounts = list(map(int, input().split()))
deadlines = list(map(int, input().split()))

print(max_money(n, amounts, deadlines))

def get_numerical_value(word):
    result = ""
    for char in word:
        result += str(ord(char) - ord('a'))
    return int(result)

def is_sum_equal(first_word, second_word, target_word):
    first_val = get_numerical_value(first_word)
    second_val = get_numerical_value(second_word)
    target_val = get_numerical_value(target_word)
    
    return first_val + second_val == target_val

first_word = input().strip()
second_word = input().strip()
target_word = input().strip()

result = is_sum_equal(first_word, second_word, target_word)
print("true" if result else "false")

import sys
from bisect import bisect_left
from collections import Counter
import heapq

def main():
    data = list(map(int, sys.stdin.read().split()))
    if len(data) < 2:
        return
    x, n = data[0], data[1]
    ps = data[2:2+n]

    # Sorted list of light positions (with boundaries 0 and x)
    lights = [0, x]

    # Multiset of gaps: counts and a max-heap (store negatives)
    counts = Counter()
    counts[x] = 1
    heap = [-x]

    out = []

    for p in ps:
        i = bisect_left(lights, p)
        left = lights[i-1]
        right = lights[i]

        # Remove old gap
        old = right - left
        counts[old] -= 1

        # Add new gaps
        g1 = p - left
        g2 = right - p
        counts[g1] += 1
        counts[g2] += 1
        heapq.heappush(heap, -g1)
        heapq.heappush(heap, -g2)

        # Insert light position
        lights.insert(i, p)

        # Get current max gap (clean lazy-deleted entries)
        while heap and counts[-heap[0]] == 0:
            heapq.heappop(heap)
        out.append(str(-heap[0]))

    print(" ".join(out))

if __name__ == "__main__":
    main()

import sys

def main():
    data = list(map(int, sys.stdin.read().split()))
    if len(data) < 3:
        print("IMPOSSIBLE")
        return

    n, x = data[0], data[1]
    a = data[2:2+n]
    if len(a) != n:
        print("IMPOSSIBLE")
        return

    pos = {}  # value -> first index seen
    for i, v in enumerate(a):
        need = x - v
        if need in pos:
            # larger index first (this matched your earlier “2 1” expectation)
            i1, i2 = i + 1, pos[need] + 1
            print(i1, i2)
            return
        if v not in pos:
            pos[v] = i

    print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

import sys

def compute_bounds(q, r):
    # low = ceil(10*q / (11*r)), high = floor(10*q / (9*r))
    num = 10 * q
    low = (num + 11 * r - 1) // (11 * r)
    high = num // (9 * r)
    if low < 1:
        low = 1
    return low, high

def max_kits(n, r, p, packages):
    ranges = []
    for i in range(n):
        ri = r[i]
        cur = []
        for q in packages[i]:
            lo, hi = compute_bounds(q, ri)
            if lo <= hi:
                cur.append((lo, hi))
        cur.sort()  # sort by (low, high)
        ranges.append(cur)

    idx = [0] * n
    kits = 0
    while True:
        # stop if any ingredient exhausted
        for i in range(n):
            if idx[i] >= len(ranges[i]):
                return kits

        # compute overlap of current ranges
        lo = max(ranges[i][idx[i]][0] for i in range(n))
        hi = min(ranges[i][idx[i]][1] for i in range(n))

        if lo <= hi:
            kits += 1
            for i in range(n):
                idx[i] += 1
        else:
            # drop the package with the smallest high
            worst = 0
            worst_high = ranges[0][idx[0]][1]
            for i in range(1, n):
                h = ranges[i][idx[i]][1]
                if h < worst_high:
                    worst_high = h
                    worst = i
            idx[worst] += 1

def parse_input_all_ints():
    nums = list(map(int, sys.stdin.read().split()))
    if not nums:
        return None
    # Try layout A: n, p, r[n], then n*p packages
    if len(nums) >= 2:
        n = nums[0]
        p = nums[1]
        if len(nums) >= 2 + n:
            r = nums[2:2 + n]
            rem = nums[2 + n:]
            if len(rem) == n * p:
                packages = []
                k = 0
                for _ in range(n):
                    row = rem[k:k + p]
                    packages.append(row)
                    k += p
                return n, r, p, packages

    # Try layout B: n, r[n], p, then n*p packages
    if len(nums) >= 1:
        n = nums[0]
        if len(nums) >= 1 + n + 1:
            r = nums[1:1 + n]
            p = nums[1 + n]
            rem = nums[2 + n:]
            if len(rem) == n * p:
                packages = []
                k = 0
                for _ in range(n):
                    row = rem[k:k + p]
                    packages.append(row)
                    k += p
                return n, r, p, packages

    # If neither matches exactly, raise a clear error
    raise ValueError("Input does not match expected formats: "
                     "[n p; r...; n lines of p] or [n; r...; p; n lines of p].")

def main():
    try:
        parsed = parse_input_all_ints()
    except ValueError as e:
        # Print 0 (or handle per your judge’s expectation) instead of crashing
        # but better to surface the error locally while developing:
        # print(0); return
        print(0)
        return
    if parsed is None:
        return
    n, r, p, packages = parsed
    print(max_kits(n, r, p, packages))

if __name__ == "__main__":
    main()

def precedence(op):
    if op in ('+', '-'):
        return 1
    if op in ('*', '/'):
        return 2
    return 0

def apply_op(a, b, op):
    if op == '+': return a + b
    if op == '-': return a - b
    if op == '*': return a * b
    if op == '/': return a // b  # integer division as per typical CP problems

def evaluate(tokens):
    values = []
    ops = []
    i = 0
    while i < len(tokens):
        if tokens[i] == ' ':
            i += 1
            continue
        elif tokens[i] == '(':
            ops.append(tokens[i])
        elif tokens[i].isdigit():
            val = 0
            while i < len(tokens) and tokens[i].isdigit():
                val = val * 10 + int(tokens[i])
                i += 1
            values.append(val)
            i -= 1
        elif tokens[i] == ')':
            while ops and ops[-1] != '(':
                b = values.pop()
                a = values.pop()
                op = ops.pop()
                values.append(apply_op(a, b, op))
            ops.pop()  # remove '('
        else:
            while ops and precedence(ops[-1]) >= precedence(tokens[i]):
                b = values.pop()
                a = values.pop()
                op = ops.pop()
                values.append(apply_op(a, b, op))
            ops.append(tokens[i])
        i += 1

    while ops:
        b = values.pop()
        a = values.pop()
        op = ops.pop()
        values.append(apply_op(a, b, op))

    return values[-1]

# Read the whole expression as a single line
expr = input().strip()
print(evaluate(expr))

import sys

def solve():
    n = int(sys.stdin.readline())
    B = list(map(int, sys.stdin.readline().split()))

    def possible(start):
        A = [0] * n
        A[0] = start
        for i in range(n - 1):
            A[i+1] = A[i] ^ B[i]
        return (A[-1] ^ A[0]) == B[-1]

    if possible(0) or possible(1):
        print("YES")
    else:
        print("NO")

t = int(sys.stdin.readline())
for _ in range(t):
    solve()

from collections import deque

def one_letter_diff(w1, w2):
    diff = 0
    for a, b in zip(w1, w2):
        if a != b:
            diff += 1
            if diff > 1:
                return False
    return diff == 1

def word_ladder(start, end, dictionary):
    dictionary = set(dictionary)
    if end not in dictionary:
        return None

    queue = deque([[start]])
    visited = {start}

    while queue:
        path = queue.popleft()
        last = path[-1]

        if last == end:
            return path

        for word in list(dictionary):
            if word not in visited and one_letter_diff(last, word):
                visited.add(word)
                queue.append(path + [word])

    return None

# --- Robust input reading ---
words = input().strip().split()
start, end = words[0], words[1]
dictionary = words[2:]

result = word_ladder(start, end, dictionary)
if result:
    print(" ".join(result))
else:
    print("null")

def solve():
    n = int(input())
    blocks = set()
    
    for _ in range(n):
        x, y = map(int, input().split())
        blocks.add((x, y))
    
    if (1, 1) in blocks or (n, n) in blocks:
        return "NO"
    
    dp = [[False] * (n + 1) for _ in range(n + 1)]
    dp[1][1] = True
    
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if (i, j) in blocks:
                continue
            if i > 1 and dp[i-1][j]:
                dp[i][j] = True
            if j > 1 and dp[i][j-1]:
                dp[i][j] = True
    
    return "YES" if dp[n][n] else "NO"

t = int(input())
for _ in range(t):
    print(solve())

# Read big matrix
N = int(input().strip())
big = [list(map(int, input().split())) for _ in range(N)]

# Read small matrix
M = int(input().strip())
small = [list(map(int, input().split())) for _ in range(M)]

found = False

# Slide over all possible top-left positions
for i in range(N - M + 1):
    for j in range(N - M + 1):
        match = True
        for x in range(M):
            for y in range(M):
                if big[i + x][j + y] != small[x][y]:
                    match = False
                    break
            if not match:
                break
        if match:
            found = True
            break
    if found:
        break

print("True" if found else "False")

def solve():
    n = int(input())
    arr = list(map(int, input().split()))

    freq = {}
    for x in arr:
        freq[x] = freq.get(x, 0) + 1

    unique_vals = sorted(freq.keys())
    beauty_values = set()

    # If any element repeats, beauty 0 is possible
    if any(c > 1 for c in freq.values()):
        beauty_values.add(0)

    # Differences between unique values
    for i in range(len(unique_vals)):
        for j in range(i):
            beauty_values.add(unique_vals[i] - unique_vals[j])

    print(len(beauty_values))


t = int(input())
for _ in range(t):
    solve()

def solve():
    n = int(input())
    arr = list(map(int, input().split()))

    freq = {}
    for x in arr:
        freq[x] = freq.get(x, 0) + 1

    unique_vals = sorted(freq.keys())
    beauty_values = set()

    # If any element repeats, beauty 0 is possible
    if any(c > 1 for c in freq.values()):
        beauty_values.add(0)

    # Differences between unique values
    for i in range(len(unique_vals)):
        for j in range(i):
            beauty_values.add(unique_vals[i] - unique_vals[j])

    print(len(beauty_values))


t = int(input())
for _ in range(t):
    solve()

import sys
input = sys.stdin.readline

def can_be_anti_palindrome(freq, length):
    if length % 2 == 1:
        return False
    for f in freq.values():
        if f > length // 2:
            return False
    return True

t = int(input())
for _ in range(t):
    n, q = map(int, input().split())
    arr = list(map(int, input().split()))

    # Precompute prefix frequency for quick queries
    pref = [[0]*(n+1) for _ in range(4)]  # since values are only 1,2,3

    for i in range(1, n+1):
        for v in (1,2,3):
            pref[v][i] = pref[v][i-1]
        pref[arr[i-1]][i] += 1

    for __ in range(q):
        L, R = map(int, input().split())
        length = R - L + 1

        # build frequency dict for subarray [L, R]
        freq = {
            1: pref[1][R] - pref[1][L-1],
            2: pref[2][R] - pref[2][L-1],
            3: pref[3][R] - pref[3][L-1],
        }

        if can_be_anti_palindrome(freq, length):
            print("Yes")
        else:
            print("No")

text = input().strip()
first = input().strip()
second = input().strip()

words = text.split()
result = []

for i in range(len(words) - 2):
    if words[i] == first and words[i+1] == second:
        result.append(words[i+2])

print('\n'.join(result))

def word_break(s, word_dict):
    word_set = set(word_dict)
    memo = {}

    def dfs(start):
        if start == len(s):
            return [""]  # one valid way: empty string
        if start in memo:
            return memo[start]

        sentences = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set:
                for sub in dfs(end):
                    if sub:
                        sentences.append(word + " " + sub)
                    else:
                        sentences.append(word)
        memo[start] = sentences
        return sentences

    return dfs(0)


# Read input
t = int(input().strip())
for _ in range(t):
    n = int(input().strip())
    dictionary = input().strip().split()
    s = input().strip()

    results = word_break(s, dictionary)
    for sentence in results:
        print(sentence)

t = int(input().strip())
tried_ingredients = set()
count = 0

for _ in range(t):
    drink = input().strip()
    # If no ingredient in this drink has been tried before
    if all(ch not in tried_ingredients for ch in drink):
        count += 1
        tried_ingredients.update(drink)

print(count)

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    s = input().strip()

    for _ in range(k):
        ns = list(s)  # next state initialized with current state

        # we use only original s for checking
        for i in range(n):
            if s[i] == '1':
                ns[i] = '0'  # current one becomes zero

                if i > 0 and s[i-1] == '0':  # flip left neighbor only if it was '0'
                    ns[i-1] = '1'
                if i < n-1 and s[i+1] == '0':  # flip right neighbor only if it was '0'
                    ns[i+1] = '1'

        # update string for next second
        new_s = ''.join(ns)
        if new_s == s:  # if no change, break early (optimization)
            break
        s = new_s

    print(s)

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    
    for i in range(len(heights)):
        while stack and heights[i] < heights[stack[-1]]:
            h = heights[stack.pop()]
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * w)
        stack.append(i)
    
    while stack:
        h = heights[stack.pop()]
        w = len(heights) if not stack else len(heights) - stack[-1] - 1
        max_area = max(max_area, h * w)
    
    return max_area

input_line = input().strip()
if input_line.startswith('[') and input_line.endswith(']'):
    heights_str = input_line[1:-1]
    heights = list(map(int, heights_str.split(',')))
else:
    heights = list(map(int, input_line.split()))

print(largestRectangleArea(heights))

t = int(input())

for _ in range(t):
    n, v = map(int, input().split())

    # Maximum cost: always refill 1 liter at every checkpoint
    max_cost = (n - 1) * n // 2

    if v >= n - 1:
        # Can reach in one full refill at checkpoint 1
        min_cost = n - 1
    else:
        # First refill full tank at checkpoint 1 (cost 1 * v)
        min_cost = v
        # Remaining liters needed
        remaining = n - 1 - v
        # Need to refill 1 liter at each next checkpoint: 2, 3, ..., (2 + remaining - 1)
        start = 2
        end = 2 + remaining - 1
        min_cost += (end * (end + 1)) // 2 - ((start - 1) * start) // 2

    print(max_cost, min_cost)

import math

def is_perfect_square(n):
    if n < 0:
        return False
    root = int(math.sqrt(n))
    return root * root == n

def is_perfect_cube(n):
    if n < 0:
        return False
    root = int(round(n ** (1/3)))
    return root ** 3 == n

def count_perfect_pairs(arr):
    n = len(arr)
    count = 0
    
    # Check all pairs (i, j) where i < j to avoid duplicates
    for i in range(n):
        for j in range(i + 1, n):
            sum_pair = arr[i] + arr[j]
            if is_perfect_square(sum_pair) or is_perfect_cube(sum_pair):
                count += 1
    
    return count

# Read input
t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    result = count_perfect_pairs(arr)
    print(result)

t = int(input())
for _ in range(t):
    s = input().strip()
    stack = []
    match = {')': '(', ']': '[', '}': '{'}
    valid = True
    for char in s:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack or stack[-1] != match[char]:
                valid = False
                break
            stack.pop()
    if stack:
        valid = False
    print("True" if valid else "False")

s = input()
stack = []
remove = set()

for i, ch in enumerate(s):
    if ch == '(':
        stack.append(i)
    elif ch == ')':
        if stack:
            stack.pop()
        else:
            remove.add(i)

remove.update(stack)

result = ""
for i in range(len(s)):
    if i not in remove:
        result += s[i]

print(result)

word = input()

vowels = "AEIOU"
valid_last = "[{}]"

is_valid = (
    len(word) >= 6 and
    not word[0].isdigit() and
    word[1] not in vowels and
    word[-1] in valid_last
)

i = 2
num1 = ""
while i < len(word) and word[i].isdigit():
    num1 += word[i]
    i += 1

vow = ""
while i < len(word) and word[i] in vowels:
    vow += word[i]
    i += 1

num2 = ""
while i < len(word) and word[i].isdigit():
    num2 += word[i]
    i += 1

if is_valid and num1 and vow and num2 and i == len(word) - 1:
    print("YES", int(num1) + int(num2))
else:
    n1 = int(num1) if num1 else 0
    n2 = int(num2) if num2 else 0
    print("NO", n1 - n2)

def int_to_roman(num):
    val = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    syms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    roman = ""
    for i in range(len(val)):
        count = num // val[i]
        roman += syms[i] * count
        num -= val[i] * count
    return roman

import math

def is_valid_set(friend_set, remaining_set):
    for x in friend_set:
        for y in remaining_set:
            if math.gcd(x, y) != 1:
                return False
    return True

def solve():
    t = int(input())
    for _ in range(t):
        n, k = map(int, input().split())
        numbers = list(range(1, n + 1))
        found = False
        from itertools import combinations
        for combo in combinations(numbers, k):
            friend_set = set(combo)
            remaining_set = set(numbers) - friend_set
            if is_valid_set(friend_set, remaining_set):
                print("YES")
                print(" ".join(map(str, friend_set)))
                found = True
                break
        if not found:
            print("NO")

solve()