Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, A):
    p = reduce(mul, A[:K], 1)
    for i, a in enumerate(A[K:]):
        np = p//A[i] * a
        if p < np:
            print('Yes')
        else:
            print('No')
        p = np


def main():
    N, K = read_int_n()
    A = read_int_n()
    (slv(N, K, A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, A):
    for i, a in enumerate(A[K:]):
        if A[i] < a:
            print('Yes')
        else:
            print('No')


def main():
    N, K = read_int_n()
    A = read_int_n()
    (slv(N, K, A))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
s = []
for _ in range(n):
    s.append(str(input()))
for i in range(n):
    s[i] = sorted(s[i])
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        if s[i] == s[j]: ans +=1
print(ans)

### FIXED CODE ###

n = int(input())
s = []
d = {}
for _ in range(n):
    s.append("".join(sorted(str(input()))))
for si in s:
    if si not in d.keys():
        d[si] = 1
    else: d[si] += 1
ans = 0
val = d.values()
for v in val:
    ans += v*(v-1)/2
print(int(ans))
### BUGGY CODE ###

n = int(input())
s = input()

cnt = 0
for i in range(1000):
    p = str(i).zfill(3)
    f1,f2,f3 = 0,0,0
    for j in range(n):
        if not f1:
            if p[0] == s[j]:
                f1 = 1
        elif not f2:
            if p[1] == s[j]:
                f2 = 1
        elif not f3:
            if p[2] == s[j]:
                f3 = 1
        else:
            break

    if f1 and f2 and f3:
        cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
s = input()

cnt = 0
for i in range(10):
    p1 = s.find(str(i))
    if p1 == -1:
        continue
    
    for j in range(10):
        p2 = s.find(str(j),p1+1)
        if p2 == -1:
            continue

        for k in range(10):
            p3 = s.find(str(k),p2+1)
            if p3 != -1:
                cnt += 1

print(cnt)
### BUGGY CODE ###

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

min=1000000000000000
for i in range(n-1):
    xy=abs(sum(a[:i+1])-sum(a[i+1:]))
    if xy < min:
        min=xy
print(min)


### FIXED CODE ###

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

min=1000000000000000
left_sum=0
right_sum=sum(a)
for i in range(n-1):
    left_sum += a[i]
    right_sum -= a[i]
    xy=abs(left_sum-right_sum)
    if xy < min:
        min=xy
print(min)
### BUGGY CODE ###

n = int(input())
a = input().split()

b = []

for e in a:
    b.append(e)
    b = b[::-1]
ans = ' '.join(b)
print(ans)


### FIXED CODE ###

n = int(input())
a = input().split()

b = []
c = []
for i in range(len(a)):
    if (i+1) % 2 !=  0:
        b.append(a[i])
    else:
        c.append(a[i])
if (i + 1) % 2 != 0:
    d = " ".join(reversed(b)) + " " + " ".join(c)
else:
    d = " ".join(reversed(c)) + " " + " ".join(b)

print(d)
### BUGGY CODE ###

n, x, y = map(int, input().split())

lis = [0]*(n-1)
for i in range(n):
    for j in range(i+1, n):
        a = j-i
        if a == 1:
            dist = 1
        else:
            b = min(abs(x-1-i), abs(y-1-i)) + 1 + min(abs(y-1-j), abs(x-1-j))
            dist = min(a, b)
        lis[dist-1] += 1

for i in lis:
    print(i)

### FIXED CODE ###

n, x, y = map(int, input().split())

lis = [0]*(n-1)
for i in range(n):
    disxi = min(abs(x-1-i), abs(y-1-i))
    for j in range(i+1, n):
        a = j-i
        if a == 1:
            dist = 1
        else:
            b = disxi + 1 + min(abs(y-1-j), abs(x-1-j))
            dist = min(a, b)
        lis[dist-1] += 1

for i in lis:
    print(i)
### BUGGY CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter

import sys
def input():
	return sys.stdin.readline().strip()

H, W = list(map(int, input().split()))

A = []
for i in range(H):
	A.append(input())

num = [[0]*W for _ in range(H)]
for i in range(H):
	for j in range(W):
		if A[i][j] == ".":
			num[i][j] = 1000000

dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def saiki(i, j, count):
	next_to = []
	#print(i, j)
	#count = copy.deepcopy(count)
	count[i][j] = 1
	for n in range(4):
		x = i + dxy[n][0]
		y = j + dxy[n][1]
		if x < H and y < W and 0 <= x and 0 <= y:
			if num[x][y] > 10000 and count[x][y] == 0:
				saiki(x, y, count)
				#print(i, j)
			next_to.append(num[x][y])
	num[i][j] = min(next_to) + 1
	#print(i, j, num[i][j], next_to,num)

count = [[0] * W for _ in range(H)]
for i in range(H):
	for j in range(W):
		if num[i][j] > 10000:

			saiki(i, j, count)

max_num = 0
for i in range(H):
	for j in range(W):
		max_num = max(max_num, num[i][j])

print(max_num)

### FIXED CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

H, W = list(map(int,input().split()))
A = []
for i in range(H):
	A.append(input())

dist = [[10000000 for i in range(W)] for j in range(H)]

now = deque()
for i in range(H):
	for j in range(W):
		if A[i][j] == "#":
			now.append([i,j])
			dist[i][j] = 0


while len(now) > 0:
	loc = now.popleft()
	if loc[0] < H - 1 and dist[loc[0] + 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0] + 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0] + 1, loc[1]])
	if loc[0] > 0 and dist[loc[0] - 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0] - 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0] - 1, loc[1]])
	if loc[1] < W - 1 and dist[loc[0]][loc[1] + 1] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0]][loc[1] + 1] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0], loc[1] + 1])
	if loc[1] > 0 and dist[loc[0]][loc[1] - 1] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0]][loc[1] - 1] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0], loc[1] - 1])

num = 0
for i in range(H):
	for j in range(W):
		num = max(num, dist[i][j])
print(num)
### BUGGY CODE ###

#-*-coding:utf-8-*-
N = int(input())
A = [int(i) for i in input().split()]

num = 1
for i in range(N):
  num = num * A[i] 

if num > 10 ** 18:
  num = -1
  
print(num)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
A.sort()
num = A[0]
for a in A[1:]:
  num *= a
  if num > 10 ** 18:
    print(-1)
    exit()
print(num)
### BUGGY CODE ###

K = int(input())
S = input()
L = len(S)

MOD = 10 ** 9 + 7
modinv = lambda a, mod=MOD: pow(a, -1, mod)

# x: 26^k*25^(K-k)
x = pow(26, K, MOD)

# comb: C(L+K-i-1, L-1)
comb = 1

ans = 0
for i in range(K, -1, -1):
    ans = (ans + comb * x) % MOD
    x = x * 25 * modinv(26) % MOD
    comb = comb * (L + K - i) * modinv(K - i + 1) % MOD
print(ans)


### FIXED CODE ###

K = int(input())
S = input()
L = len(S)

MOD = 10 ** 9 + 7
modinv = lambda a, mod=MOD: pow(a, MOD - 2, mod)

# x: 26^k*25^(K-k)
x = pow(26, K, MOD)

# comb: C(L+K-i-1, L-1)
comb = 1

ans = 0
for i in range(K, -1, -1):
    ans = (ans + comb * x) % MOD
    x = x * 25 * modinv(26) % MOD
    comb = comb * (L + K - i) * modinv(K - i + 1) % MOD
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
cnt=0
r=s.count("R")
g=s.count("G")
b=s.count("B")

ans=r*g*b

for i in range(n):
    for j in range(n):
        if s[i]!=s[j]:
            if j-i<=n//2:
                if i<j:
                    for k in range(n):
                        if s[k]!=s[j] and s[i]!=s[k]:   
                            if j<k:
                                if j-i==k-j:
                                    ans-=1

            else:
                break        
print(ans)
        

### FIXED CODE ###

n=int(input())
s=input()
cnt=0
r=s.count("R")
g=s.count("G")
b=s.count("B")

ans=r*g*b

for i in range(n):
    for j in range(n):
        if s[i]!=s[j]:
            if j-i<=n//2:
                if i<j:
                    d=j-i
                    k=j+d
                    if k<n:
                        if s[k]!=s[j] and s[i]!=s[k]:
                            ans-=1
                        

      
print(ans)
### BUGGY CODE ###

# from pprint import pprint
# import math
# import collections
from numba import jit

N = int(input())

loops = 0


# n, k = map(int, input().split(' '))
# a = list(map(int, input().split(' ')))

@jit('i8(i8,i8,i8)', cache=True)
def calc(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


# 全数字が等しい場合
p_eq = []
for xyz in range(1, 100):
    loops += 1
    p_eq.append(calc(xyz, xyz, xyz))

p_ne = []
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            res = calc(x, y, z)
            p_ne.append(res)

# p_set = p

# p_equal = []
# p_nonequal = []
# for _p in p_set:
#     loops += 1
#     x, y, z = _p[0], _p[1], _p[2]
#
#     if x == y == z:
#         p_equal.append(calc(x, y, z))
#     else:
#         p_nonequal.append(calc(x, y, z))

# print(p_equal)
# print(p_nonequal)

for i in range(1, N + 1):
    loops += 1
    if i in p_eq:
        print(1)
    elif i in p_ne:
        print(3)
    else:
        print(0)

# print('lp', loops)


### FIXED CODE ###

# from pprint import pprint
# import math
# import collections
from numba import jit

N = int(input())

# n, k = map(int, input().split(' '))
# a = list(map(int, input().split(' ')))

@jit(cache=True)
def calc(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


res = [0] * 1000009

for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            n = calc(x, y, z)
            res[n - 1] += 1

for i in range(N):
    print(res[i])
### BUGGY CODE ###

from operator import add, mul, sub, or_


class BIT:
    def __init__(self, n, op, ie):
        self.n = n
        self.tree = [ie]*(n+1)
        self.op = op

    def update(self, i, v):
        while i <= self.n:
            self.tree[i] = self.op(self.tree[i], v)
            i += i & (-i)

    def query(self, i):
        v = 0
        while i:
            v = self.op(self.tree[i], v)
            i -= i & (-i)
        return v


N, Q = map(int, input().split())
*c, = map(int, input().split())

q = [[] for _ in range(N+1)]
for i in range(Q):
    x, y = map(int, input().split())
    q[y-1].append([i, x-1])

bit = BIT(N, add, 0)
finds = [-1]*(N+1)
ans = [0]*Q
for i in range(N):
    if finds[c[i]] != -1:
        bit.update(finds[c[i]]+1, -1)

    finds[c[i]] = i
    bit.update(finds[c[i]]+1, 1)

    for j, x in q[i]:
        ans[j] = bit.query(i+1) - bit.query(x)

for a in ans:
    print(a)


### FIXED CODE ###

from operator import add, mul, sub, or_


class SegmentTree:
    '''
    セグメント木(遅延ではない)
    1-indexd セグメント木
    values : 値の配列
    op : 区間に対する関数
    ie : 初期値
    '''

    def __init__(self, values):
        self.values = values
        vlen = len(values)
        self.size = 2 ** (vlen-1).bit_length()
        self.tree = [0]*self.size + self.values + [0]*(self.size-vlen)

        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.tree[i*2] + self.tree[i*2+1]

    def update(self, i, v):
        i += self.size
        self.tree[i] = v
        while i > 0:
            i //= 2
            self.tree[i] = self.tree[i*2] + self.tree[i*2+1]

    def query(self, l, r):
        l += self.size
        r += self.size
        ret = 0
        while l < r:
            if l & 1:
                ret += self.tree[l]
                l += 1
            if r & 1:
                r -= 1
                ret += self.tree[r]
            l //= 2
            r //= 2
        return ret


N, Q = map(int, input().split())
*c, = map(int, input().split())

q = [[] for _ in range(N+1)]
for i in range(Q):
    x, y = map(int, input().split())
    q[y-1].append([i, x-1])

st = SegmentTree([0]*(N+1))
finds = [-1]*(N+1)
ans = [0]*Q
for i in range(N):
    if finds[c[i]] != -1:
        st.update(finds[c[i]], 0)

    finds[c[i]] = i
    st.update(finds[c[i]], 1)

    for j, x in q[i]:
        ans[j] = st.query(x, i+1)

for a in ans:
    print(a)
### BUGGY CODE ###

N,S = map(int,input().split())
A = list(map(int,input().split()))
MOD=998244353

#まだ左端を選択していない状態(状態 0)。この時は和が0の時1通りでそれ以外は0。
#左端は選択済みだけど右端は選択していない状態(状態 1)
#右端も選択済みの状態(状態 2)

dp = [[[0 for _ in range(3)] for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
#i個目までで和がjとなる場合の数
ans = 0

for i in range(N):
  for j in range(S+1):
    #from 0
    #if j == 0: #j==0の時以外は基本0なのであってもなくても良い。
    dp[i+1][j][0] += dp[i][j][0]%MOD
    if j+A[i] <= S:# and j == 0: #j==0の時以外は基本0なのであってもなくても良い。
      dp[i+1][j+A[i]][1] = (dp[i+1][j+A[i]][1]+dp[i][j][0] * (i+1))%MOD
      dp[i+1][j+A[i]][2] = (dp[i+1][j+A[i]][2]+dp[i][j][0] * (i+1) * (N-i))%MOD
    #from 1
    dp[i+1][j][1] = (dp[i+1][j][1]+dp[i][j][1])%MOD
    if j+A[i] <= S:
      dp[i+1][j+A[i]][1] = (dp[i+1][j+A[i]][1]+dp[i][j][1])%MOD
      dp[i+1][j+A[i]][2] = (dp[i+1][j+A[i]][2]+dp[i][j][1] * (N-i))%MOD
    #from 2
    dp[i+1][j][2] += dp[i][j][2]%MOD
#print(dp)MODDD
print(dp[N][S][2]%MOD)
      

### FIXED CODE ###

N,S = map(int,input().split())
A = list(map(int,input().split()))
MOD=998244353

Q = [0 for _ in range(S+1)]
ans = 0
for i in range(N):
  Q[0] += 1
  Q2 = [0 for _ in range(S+1)]
  for j in range(S+1):
    Q2[j] += Q[j]%MOD
    if j+A[i] <= S: #(1+x^A[i])をかけてもx^sを超えないときに限り。
      Q2[j+A[i]] += Q[j]%MOD
  Q = Q2
  ans += Q[S]%MOD
ans = ans %MOD
print(ans)
### BUGGY CODE ###

n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
p = 10**9+7
DP = [0 for s in range(1 << n)]
DP[0] = 1
for s in range(1, 1 << n):
    l = bin(s).count('1')
    for i in range(n):
        if ((1 << i) & s) * A[l-1][i]:
            DP[s] += DP[~(1 << i) & s]
print(DP[(1 << n)-1]%p)

### FIXED CODE ###

def main():
    n = int(input())
    A = [list(map(int, input().split())) for i in range(n)]
    p = 10**9+7
    DP = [0 for s in range(1 << n)]
    DP[0] = 1
    for s in range(1, 1 << n):
        l = bin(s).count('1')
        for i in range(n):
            if ((1 << i) & s) * A[l-1][i]:
                DP[s] += DP[~(1 << i) & s]
    print(DP[(1 << n)-1] % p)


main()
### BUGGY CODE ###

n=int(input())
s=input()
m=len(s)
mod=10**9+7
dp=[[0]*(n+1) for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    for j in range(n+1):
        if j==0:
            dp[i][j]+=dp[i-1][j]+dp[i-1][j+1]
        elif j==n:
            dp[i][j]+=dp[i-1][j-1]*2
        else:
            dp[i][j]+=dp[i-1][j-1]*2+dp[i-1][j+1]
        dp[i][j]%=mod
def div(a,b):
    return (a*pow(b,mod-2,mod))%mod
print(div(dp[n][m],pow(2,m)))


### FIXED CODE ###

n=int(input())
s=input()
m=len(s)
mod=10**9+7
dp=[[0]*(n+1) for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    for j in range(n+1):
        if j==0:
            dp[i][j]+=dp[i-1][j]+dp[i-1][j+1]
        elif j==n:
            dp[i][j]+=dp[i-1][j-1]*2
        else:
            dp[i][j]+=dp[i-1][j-1]*2+dp[i-1][j+1]
        dp[i][j]%=mod
def div(a,b):
    return (a*pow(b,mod-2,mod))%mod
print(div(dp[n][m],pow(2,m)))
### BUGGY CODE ###

def main():
    import numpy as np
    import sys
    input=sys.stdin.readline
    inf=10**11
    
    a,b,q=map(int,input().split())
    S=np.array([-inf]+[int(input()) for _ in range(a)]+[inf])
    T=np.array([-inf]+[int(input()) for _ in range(b)]+[inf])
    Q=np.array([int(input()) for _ in range(q)])
    idxs=np.searchsorted(S,Q)
    idxt=np.searchsorted(T,Q)
    
    for i in range(q):
        x=Q[i]
        s=idxs[i]
        t=idxt[i]
        ans=inf
        ans=min(ans,max(T[t],S[s])-x)
        ans=min(ans,S[s]-T[t-1]+min(S[s]-x,x-T[t-1]))
        ans=min(ans,x-min(S[s-1],T[t-1]))
        ans=min(ans,T[t]-S[s-1]+min(T[t]-x,x-S[s-1]))
        print(ans)
        
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    INF=10**11
    from bisect import bisect_left
    a,b,q=map(int,input().split())
    S=[-INF]+[int(input()) for _ in range(a)]+[INF]
    T=[-INF]+[int(input()) for _ in range(b)]+[INF]

    for _ in range(q):
        x=int(input())
        s=bisect_left(S,x)
        t=bisect_left(T,x)
        ans=max(T[t],S[s])-x
        ans=min(ans,S[s]-T[t-1]+min(S[s]-x,x-T[t-1]))
        ans=min(ans,x-min(S[s-1],T[t-1]))
        ans=min(ans,T[t]-S[s-1]+min(T[t]-x,x-S[s-1]))
        print(ans)
if __name__=='__main__':
    main()
### BUGGY CODE ###

N=int(input())
S=input()

cnt=0
for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]!=S[j]:
            for k in range(j+1,N):
                if k==2*j-i:
                    continue             
                if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]  and j-i!=k-j:
                    cnt+=1

print(cnt)


### FIXED CODE ###

N=int(input())
S=input()

r=S.count('R')
g=S.count('G')
b=S.count('B')

cnt=0
for i in range(N):
    for j in range(i+1,N):
        k=j+j-i
        if k>=N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            cnt+=1

print((r*g*b)-cnt)
### BUGGY CODE ###

N,M=map(int,input().split())
import heapq
A=list(map(int,input().split()))
heapq.heapify(A)
for i in range(M):
  B,C=map(int,input().split())
  for i in range(B):
    x=heapq.heappop(A)
    if x<C:
      heapq.heappush(A,C)
    else:
      heapq.heappush(A,x)
      break
print(sum(A))      

### FIXED CODE ###

N,M=map(int,input().split())
import heapq
A=list(map(int,input().split()))
heapq.heapify(A)
BC=[]
for i in range(M):
  B,C=map(int,input().split())
  BC.append((B,C))
BC.sort(key=lambda x:x[1],reverse=True)
import bisect
A.sort()
now=0
D=[0]*N
for i in range(M):
  B=BC[i][0]
  C=BC[i][1]
  for j in range(now,min(now+B,N)):
    D[j]=C
  now+=B
  if now>N-1:
    break

for i in range(N):
  a=A[i]
  d=D[i]
  if d>a:
    A[i]=d
  else:
    break
print(sum(A))
### BUGGY CODE ###

N = int(input())
P_lis = list(map(int,input().split()))

count = 0
for i in range(N):
  check_lis = []
  for j in range(i):
    if P_lis[i] <= P_lis[j]:
      check_lis.append(1)
    else:
      check_lis.append(0)
  if all(check_lis) == 1:
    count += 1

print(count)

### FIXED CODE ###

N = int(input())
P_lis = list(map(int, input().split()))
 
dummy = 2*10**5
answer = 0
 
for p in P_lis:
  if p <= dummy:
    answer += 1
    dummy = p
print(answer)
### BUGGY CODE ###

mod = 10**6 + 3

fac = [0]*mod
fac[0] = 1
for i in range(1, mod):
    fac[i] = fac[i - 1] * i
    fac[i] %= mod

def gcd(a, b):
    def calc(a, b, first, second):
        if a < b:
            a, b = b, a
        r = a % b
        q = -(a - r)/b
        if r == 0:
            return b, second
        # first += q * second
        first = [x + q * y for (x, y) in zip(first, second)]
        return calc(r, b, second, first)
    first = [1, 0]
    second = [0, 1]
    return calc(a, b, first, second)

def mod_inv(n, mod):
    table = gcd(n, mod)
    inv = table[1][1]
    if inv < 0:
        inv += mod
    return inv

def mod_pow(x, n, mod):
    ret = 1
    while n > 0:
        if n & 1 != 0:
            ret *= x
            ret %= mod
        x *= x
        x %= mod
        n >>= 1
    return ret

l = raw_input().split()
Q = int(l[0])
X = []
D = []
N = []
for i in range(Q):
    l = raw_input().split()
    X.append(int(l[0]))
    D.append(int(l[1]))
    N.append(int(l[2]))


for i in range(Q):
    x = X[i]
    d = D[i]
    n = N[i]
    if d == 0:
        print(mod_pow(x, n, mod))
        continue
    inv_d = mod_inv(d, mod)
    x_d = (x * inv_d) % mod
    # print(i, x, d, n, inv_d, x_d, x_d + n - 1, d_n)
    if x_d + n - 1 >= mod:
        print(0)
        continue
    ans1 = fac[x_d + n - 1]
    ans2 = fac[x_d - 1]
    # print(ans1, ans2)
    ans = ans1 * mod_inv(ans2, mod)
    ans %= mod
    d_n = mod_pow(d, n, mod)
    ans = ans * d_n
    ans %= mod
    print(ans)

### FIXED CODE ###

mod = 10**6 + 3

fac = [0]*mod
fac[0] = 1
for i in range(1, mod):
    fac[i] = fac[i - 1] * i
    fac[i] %= mod

def gcd(a, b):
    def calc(a, b, first, second):
        if a < b:
            a, b = b, a
        r = a % b
        q = -(a - r)//b
        if r == 0:
            return b, second
        # first += q * second
        first = [x + q * y for (x, y) in zip(first, second)]
        return calc(r, b, second, first)
    first = [1, 0]
    second = [0, 1]
    return calc(a, b, first, second)

def mod_inv(n, mod):
    table = gcd(n, mod)
    inv = table[1][1]
    if inv < 0:
        inv += mod
    return inv

def mod_pow(x, n, mod):
    ret = 1
    while n > 0:
        if n & 1 != 0:
            ret *= x
            ret %= mod
        x *= x
        x %= mod
        n >>= 1
    return ret

l = input().split()
Q = int(l[0])
X = []
D = []
N = []
for i in range(Q):
    l = input().split()
    X.append(int(l[0]))
    D.append(int(l[1]))
    N.append(int(l[2]))


for i in range(Q):
    x = X[i]
    d = D[i]
    n = N[i]
    if d == 0:
        print(mod_pow(x, n, mod))
        continue
    inv_d = mod_inv(d, mod)
    x_d = (x * inv_d) % mod
    # print(i, x, d, n, inv_d, x_d, x_d + n - 1)
    if x_d + n - 1 >= mod:
        print(0)
        continue
    ans1 = fac[x_d + n - 1]
    ans2 = fac[x_d - 1]
    # print(ans1, ans2)
    ans = ans1 * mod_inv(ans2, mod)
    ans %= mod
    d_n = mod_pow(d, n, mod)
    ans = ans * d_n
    ans %= mod
    print(ans)