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

import sys

sys.setrecursionlimit(10001)


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


memo = {}


def dfs(i, remain):
    # i: number of person of group
    if remain == 0:
        return 1
    if i > b or i > remain:
        return 0
    if (i, remain) in memo:
        return memo[i, remain]

    ret = dfs(i + 1, remain)

    for j in range(c, d + 1):
        ij = i * j
        if ij > remain:
            break
        pattern = dfs(i + 1, remain - ij)
        new_pattern = pattern * facts[remain] * invs[remain - ij] % MOD
        new_pattern = new_pattern * pow(invs[i], j, MOD) * invs[j]
        ret = (ret + new_pattern) % MOD

    memo[i, remain] = ret
    return ret


n, a, b, c, d = map(int, input().split())
MOD = 10 ** 9 + 7
facts, invs = prepare(n, MOD)
print(dfs(a, n))


### FIXED CODE ###

def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv = inv * m % MOD
        invs[m - 1] = inv

    return factorials, invs


def solve(n, a, b, c, d, MOD):
    facts, invs = prepare(n, MOD)
    dp = [0] * (n + 1)
    dp[n] = 1
    for i in range(a, b + 1):
        iv = invs[i]
        for j in range(i * c, n + 1):
            base = dp[j] * facts[j] % MOD
            for k in range(c, d + 1):
                ik = i * k
                if ik > j:
                    break
                pat = base * invs[j - ik] % MOD
                pat = pat * pow(iv, k, MOD) * invs[k]
                dp[j - ik] = (dp[j - ik] + pat) % MOD
    return dp[0]


n, a, b, c, d = map(int, input().split())
MOD = 10 ** 9 + 7
print(solve(n, a, b, c, d, MOD))
### BUGGY CODE ###

import collections
import math


def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

summ = 0
for v in c.values():
    summ += comb(v, 2)

for i in range(n):
    print(summ - comb(c[a[i]], 2) + comb(c[a[i]] - 1, 2))

### FIXED CODE ###

import collections
import math


def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


input()
a = list(map(int, input().split()))
c = collections.Counter(a)

summ = sum([comb(v, 2) for v in c.values()])
for ai in a:
    print(summ - c[ai] + 1)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A.sort()
F.sort(reverse=True)

def is_ok(m):
    c = 0
    for a,f in zip(A,F):
        d = m//f
        c += max(0, a-d)
        if c > K:
            return False
    return True

ok = 10**13
ng = -1
while ok-ng > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
F = list(map(int,input().split()))
F.sort(reverse=True)

sa = sum(A)
if K >= sa:
    print(0)
    exit()

def isok(b):
    k = 0
    for a,f in zip(A,F):
        if a > b//f:
            k += a-(b//f)
            if k > K:
                return False
    return True

ok = 10**12+1
ng = 0

while ok-ng > 1:
    m = (ok+ng)//2
    if isok(m):
        ok = m
    else:
        ng = m
print(ok)
### BUGGY CODE ###

import collections
import sys

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


if d[0]!=0:
    print(0)
    sys.exit(0)

p=1

for i in range(1,max(d)+1):
    if d.count(i)==0:
        print(0)
        sys.exit(0)
    elif d[i]==0:
        print(0)
        sys.exit(0)
    else:
        p = (p * pow(d.count(i-1), d.count(i), 998244353))%998244353

print(p)

### FIXED CODE ###

import collections
import sys

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

cnt = collections.Counter(d)

if d[0]!=0:
    print(0)
    sys.exit(0)

if cnt[0]!=1:
    print(0)
    sys.exit(0)    
    
p = 1

for i in range(1,max(d)+1):
    if cnt[i] == 0:
        print(0)
        sys.exit(0)  
    else:
        p = (p * pow(cnt[i-1], cnt[i], 998244353))%998244353

print(p)
### BUGGY CODE ###

import collections

n = int(input())
s = [input() for i in range(n)]

s_count = collections.Counter(s)

values = []
ans = []

for key in list(s_count.keys()):
    values.append(s_count.get(key))

for key in list(s_count.keys()):
    if s_count.get(key) == max(values):
        ans.append(key)

ans.sort()

for word in ans:
    print(word)

### FIXED CODE ###

import collections

n = int(input())
s = [input() for i in range(n)]

s_count = collections.Counter(s)
largest = max(list(s_count.values()))
ans = []

for key in list(s_count.keys()):
    if s_count.get(key) == largest:
        ans.append(key)

ans.sort()

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

import numpy as np


def calc_mul4_dp(n, aaa):
    dp = np.array([list(range(16))] * (n + 1), dtype=np.int64)

    next_a = aaa[-1]
    for i in range(n - 2, -1, -1):
        a = aaa[i]
        if a > next_a:
            cnt = 0  # a[i]以上になるためにa[i+1]に4をかけなければならない最小回数
            b = next_a
            while a > b:
                b <<= 2
                cnt += 1
            dp[i, :-cnt] += dp[i + 1, cnt:]
            dp[i, -cnt:] += dp[i + 1, -1] + np.arange(1, cnt + 1) * (n - i - 1)
        else:
            cnt = 0  # a[i]に4をかけても次に影響が出ない最大回数
            b = a
            while next_a >= b:
                b <<= 2
                cnt += 1
            cnt -= 1
            dp[i, :cnt] += dp[i + 1, 0]
            dp[i, cnt:] += dp[i + 1, :16 - cnt]
        next_a = a
    return dp


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    mul4dp = (fdp.T[0] + bdp.T[0]) * 2
    return (mul4dp + np.arange(n + 1)).min()


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))


### FIXED CODE ###

import numpy as np


def calc_mul4_dp(n, aaa):
    # dp[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    # (支配的な数, ←をいじらなかった場合の支配区間の最後の数, 最初の数の位置)
    stack = [(10 ** 20, 10 ** 20, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 19
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, e, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][2] - j)
            c = min(e << (2 * mul), INF)
        stack.append((a, c, i))
        result.append(inc)
        # print(a, stack, result)
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    # aaa = [1, 10 ** 9] * (n // 2)
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    # print(aaa)
    print(solve(n, aaa))


# test()

n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))
### BUGGY CODE ###

import math
n=int(input())
for i in range(1,n+1):
    p=int(math.sqrt(i))
    k=0
    for x in range(1,p+1):
        for y in range(1,p+1):
            for z in range(1,p+1):
                if x**2+y**2+z**2+x*y+y*z+z*x==i:
                    k+=1
    print(k)

### FIXED CODE ###

import math
n=int(input())
j=int(math.sqrt(n))
k=[0]*n
for x in range(1,j+1):
     for y in range(1,j+1):
        for z in range(1,j+1):
            p=x**2+y**2+z**2+x*y+y*z+z*x
            if p<=n:
                k[p-1]+=1
[print(i)for i in k]
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, mod = 10**5+1, 10**9+7
fac = [1, 1] + [None] * N
inv = [0, 1] + [None] * N
facInv = [1, 1] + [None] * N
for i in range(2, N+1):
    fac[i] = i * fac[i-1] % mod
    inv[i] = mod-(inv[mod%i]*(mod//i))%mod
    facInv[i] = facInv[i-1]*inv[i]%mod
def modCom(n, k):
    return 0 if n < k else fac[n] * facInv[k] * facInv[n-k] % mod
n = int(input())
a = list(map(int, input().split()))
for x in range(1, n+1):
    if a.count(x) == 2: break
fi = a.index(x) + 1
si = a[fi:].index(x) + fi + 1
print(n)
for k in range(2, n+1):
    print((modCom(n+1, k) - modCom(fi+n-si, k-1)) % mod)
print(1)


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N, mod = 10**5+1, 10**9+7
fac = [1, 1] + [None] * N
inv = [0, 1] + [None] * N
facInv = [1, 1] + [None] * N
for i in range(2, N+1):
    fac[i] = i*fac[i-1]%mod
    inv[i] = mod-(inv[mod%i]*(mod//i))%mod
    facInv[i] = facInv[i-1]*inv[i]%mod
def modCom(n, k):
    return 0 if n < k else fac[n] * facInv[k] * facInv[n-k] % mod
n = int(input())
a = list(map(int, input().split()))
dic = defaultdict(int)
for i, x in enumerate(a):
    if dic[x] > 0:
        fi = dic[x]
        si = i+1
        break
    dic[x] = i+1
print(n)
for k in range(2, n+1):
    print((modCom(n+1, k) - modCom(fi+n-si, k-1)) % mod)
print(1)
### BUGGY CODE ###

from fractions import gcd
class SegmentTree(object):
    def __init__(self, sequence, function, identity):
        N = len(sequence)
        self.length = (1 << (N - 1)).bit_length()
        self.data = [identity] * (self.length << 1)
        self.function = function
        self.identity = identity
        for i in range(N):
            self.data[i + self.length - 1] = sequence[i]
        for i in range(self.length - 2, -1, -1) :
            self.data[i] = self.function(self.data[(i << 1) + 1], self.data[(i << 1) + 2])

    def query(self, p=None, q=None):
        if p == None:
            p = 0
        if q == None:
            q = self.length
        if q <= p:
            return self.identity
        p += self.length - 1
        q += self.length - 2
        res = self.identity
        while q - p > 1:
            if not p & 1:
                res = self.function(res, self.data[p])
            if q & 1:
                res = self.function(res, self.data[q])
                q -= 1
            p >>= 1
            q = (q - 1) >> 1
        return self.function(res, self.data[p]) if p == q else self.function(self.function(res, self.data[p]), self.data[q])

MOD = 10 ** 9 + 7
def lcm(x, y):
    return (x * y) // gcd(x, y)
input()
A = list(map(int, input().split()))
seg_tree = SegmentTree(A, lcm, 1)
l = seg_tree.query()
total = 0
for a in A:
    total = (total + l // a) % MOD
print(total)

### FIXED CODE ###

import sys
from fractions import gcd

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

def lcm(x, y):
    return (x * y) // gcd(x, y)

input()
A = list(map(int, input().split()))

l = 1
for a in A:
    l = lcm(l, a)

total = 0
for a in A:
    total += l // a

print(total % LARGE)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
import fractions
from functools import reduce

def gcd(*numbers):
    return abs(reduce(fractions.gcd, numbers))
ans = 0
for i in range(N):
    temp = A[:i] + A[i+1:]
    ans = max(ans, gcd(*temp))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
import fractions
from functools import reduce

def gcd(*numbers):
    return abs(reduce(fractions.gcd, numbers))

L = [A[0]]
R = [A[-1]]
A_R = A[::-1]
for i in range(1, N):
    L.append(fractions.gcd(L[-1], A[i]))
    R.append(fractions.gcd(R[-1], A_R[i]))
R = R[::-1]
ans = R[1]
R.append(0)
for i in range(N - 1):
    ans = max(ans, fractions.gcd(L[i],R[i+2]))
print(ans)
### BUGGY CODE ###

k = int(input())


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


ans = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        for l in range(1, k + 1):
            ans += gcd(gcd(i, j), l)
print(ans)


### FIXED CODE ###

k = int(input())


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


ans = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        for l in range(1, k + 1):
            ans += gcd(gcd(i, j), l)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
edges=[set() for i in range(n+1)]
for i in range(m):
	a,s=map(int,input().split())
	edges[a].add(s)
	edges[s].add(a)
for i in range(2,n):
	if i in edges[1]&edges[n]:
		print("POSSIBLE");exit()
print("IMPOSSIBLE")

### FIXED CODE ###

n,m=map(int,input().split())
edges=[set() for i in range(n+1)]
for i in range(m):
	a,s=map(int,input().split())
	edges[a].add(s)
	edges[s].add(a)
for i in range(2,n):
	if i in edges[1] and i in edges[n]:
		print("POSSIBLE");exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

n, h, *t=map(int,open(0).read().split())
a = sorted(t[::2])
b = sorted(t[1::2])
b_high = [i for i in b if i >= max(a)]
if (h - sum(b_high)) % a[-1] == 0:
  print(len(b_high) + (h - sum(b_high)) // a[-1])
else:
  print(len(b_high) + ((h - sum(b_high)) // a[-1]) + 1)

### FIXED CODE ###

n, h, *t=map(int,open(0).read().split())
a = t[::2]
b = t[1::2]
ma = max(a)
b_high = [i for i in b if i > ma]
if sum(b_high) > h:
  ans = 0
  b_high = sorted(b_high)
  while h > 0:
    h = h - b_high.pop()
    ans += 1
  print(ans)
else:
  if (h - sum(b_high)) % ma == 0:
    print(len(b_high) + (h - sum(b_high)) // ma)
  else:
    print(len(b_high) + ((h - sum(b_high)) // ma) + 1)
### BUGGY CODE ###

import itertools
N = int(input().strip())
seq_list = [''.join(sorted(input().strip())) for _ in range(N)]
print(len([1 for i,j in itertools.combinations(range(N), 2) if seq_list[i] == seq_list[j]]))

### FIXED CODE ###

import itertools
N = int(input().strip())
seq_list = [''.join(sorted(input().strip())) for _ in range(N)]
hash = {}
result = 0
for seq in seq_list:
  if seq in hash:
    result += hash[seq]
    hash[seq] += 1
  else:
    hash[seq] = 1
print(result)
### BUGGY CODE ###

n,m=map(int,input().split())
lst=[[] for i in range(n+1)]
prev=[]

for i in range(m):
  x,y=map(int,input().split())
  lst[x].append(y)
  prev.append([x,y])
  
for i in lst:
  i.sort()
  
for i in prev:
  s,t=i[0],i[1]
  x=lst[s].index(t)+1
  
  s,x=str(s),str(x)
  
  while len(s)<6:
    s='0'+s

  while len(x)<6:
    x='0'+x

  print(s+x)

### FIXED CODE ###

import bisect

n,m=map(int,input().split())

x=[list(map(int,input().split())) for i in range(m)]

lst=[[] for i in range(n)]

for i,v in x:
    lst[i-1].append(v)

for i in range(n):
    lst[i].sort()

for i,v in x:
    z=bisect.bisect_left(lst[i-1],v)+1

    print('0'*(6-len(str(i)))+str(i)+'0'*(6-len(str(z)))+str(z))
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
count = 0
for i in range(N):
    minP = min(P[:i+1])
    if P[i] == minP:
        count = count + 1
print(count)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
count = 0
minP = P[0]
for i in range(N):
    if P[i] <= minP:
        count += 1
        minP = P[i] 

print(count)
### BUGGY CODE ###

def resolve():
    K, S = map(int, input().split())
    ans = 0
    for i in range(K+1):
        for j in range(K+1):
            for p in range(K+1):
                if i+j+p == S:
                    ans += 1
    print(ans)
resolve()

### FIXED CODE ###

def resolve():
    K, S = map(int, input().split())
    ans = 0
    for i in range(K+1):
        for j in range(K+1):
            if 0 <= S-i-j <= K:
                ans += 1
    print(ans)
resolve()
### BUGGY CODE ###

import numpy as np

h, w = map(int, input().split())

board = [[(i+j+1) % 2 for i in range(w)] for j in range(h)]
print(np.sum(board))

### FIXED CODE ###

import numpy as np

h, w = map(int, input().split())

if h == 1 or w == 1:
  print(1)
else:
  print(int(np.ceil(h*w/2)))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000)

def f(a):
  global R,G,B,N,ans,Rm,Gm,Bm

  for b in range(N-R*a+1):
    cmod=(N-R*a-G*b)%B
    c=(N-R*a-G*b)//B
    if cmod==0 and  c>=0:
      ans+=1

  if a>0:
    f(a-1)


R,G,B,N=list(map(int,input().split(" ")))
Rm=N//R
Gm=N//G
Bm=N//B

ans=0

f(Rm)

print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)

def f(a):
  global R,G,B,N,ans,Rm,Gm,Bm

  for b in range(N-R*a+1):
    cmod=(N-R*a-G*b)%B
    c=(N-R*a-G*b)//B
    if cmod==0 and  c>=0:
      ans+=1
    elif c<0:
      break

  if a>0:
    f(a-1)


R,G,B,N=list(map(int,input().split(" ")))

ans=0

f(N//R+1)

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

def main():
    n = int(input())
    count = 0
    lists =[]

    for i in range(n):
        input_data = ''.join(sorted(input()))
        if input_data in lists:
            count = count + lists.count(input_data)
            lists.append(input_data)
        else:
            lists.append(input_data)

    print(count)


if __name__ == '__main__' :
    main()

### FIXED CODE ###

from collections import Counter

n = int(input())
count = 0
lists =[]
count_dict = Counter()

for i in range(n):
    input_data = ''.join(sorted(input()))
    if input_data in count_dict:
        count += count_dict[input_data]
        count_dict[input_data] += 1
    else:
        count_dict[input_data] = 1

print(count)
### BUGGY CODE ###

def main():
    from collections import deque
    from itertools import combinations

    N, M = map(int, input().split())

    g = tuple(set() for _ in range(N))
    for idx in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, c, idx))  # to,weight,idx
        g[b].add((a, c, idx))  # to,weight,idx

    not_used_edge = [True] * M

    for frm, to in combinations(range(N), r=2):
        dq = deque()
        dq.append((frm, 0))

        dist = [1000 * 100 + 10] * N
        dist[frm] = 0
        while dq:
            v, c = dq.popleft()
            if dist[v] < c: continue
            for u, dc, idx in g[v]:
                if dist[u] > c + dc:
                    dist[u] = c + dc
                    dq.append((u, dist[u]))

        dq = deque()
        dq.append((to, 0))
        while dq:
            v, b = dq.popleft()
            if v == frm:
                for j in range(M):
                    if (b >> j) & 1:
                        not_used_edge[j] = False
                continue

            for u, dc, idx in g[v]:
                if dist[u] == dist[v] - dc:
                    dq.append((u, b | 1 << idx))

    print(sum(not_used_edge))


if __name__ == '__main__':
    main()


### FIXED CODE ###

inf = 1000 * 1000 + 10

n, m = map(int, input().split())

g = tuple([inf] * n for _ in range(n))
e = set()
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    e.add((a, b, c))

for i in range(n):
    g[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

# print(g)

need = set()
for a, b, c in e:
    for s in range(n):
        for t in range(n):
            if g[s][t] == g[s][a] + c + g[b][t]:
                need.add((a, b))
                break
        else:
            continue
        break
# print(need)
print(m - len(need))
### BUGGY CODE ###

n,m=map(int,input().split())
dem=[]
li=[]
isl=[0]*(n-1)
ans=0
for i in range(m):
    a,b=map(int,input().split())
    dem.append([a,b])
while len(dem)!=0:   
    for j in range(len(dem)):
        for k in range(dem[j][0],dem[j][1]):
            isl[k-1]+=1
        x=max(isl)
        y=isl.index(x)+1
    for l in range(len(dem)):
        if dem[l][0]>y or dem[l][1]<=y:
          li.append([dem[l][0],dem[l][1]])
    dem=li
    ans+=1
    isl=[0]*(n-1)  
    li=[]
      
print(ans)                
        

### FIXED CODE ###

n,m=map(int,input().split())
dem=[]
ans=[]
for i in range(m):
    a,b=map(int,input().split())
    dem.append([a,b])
dem=sorted(dem,key=lambda x:x[1])  
for i in range(m):
    if len(ans)==0:
        ans.append(dem[i][1]-1)
    else:
        if ans[-1]<dem[i][0]:
            ans.append(dem[i][1]-1)  
print(len(ans))
### BUGGY CODE ###



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

a = [0] * (N - 1)
b = [0] * (N - 1)

p = [0] * Q
x = [0] * Q

point = [0] * N

def kasan(n, y):
    z = 0
    for i in range(Q):
        
        if p[i] == n:
            z += x[i]
    for i in range(N - 1):
        if a[i] == n:
            kasan(b[i],y + z)
    
    point[n - 1] += y + z

for i in range(N - 1):
    a[i],b[i] = map(int,input().split())

for i in range(Q):
    p[i],x[i] = map(int, input().split())

kasan(1,0)

print(" ".join(map(str,point)))

            



### FIXED CODE ###



import collections
N, Q = map(int, input().split())
g = [set() for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].add(b)
    g[b].add(a)

parent = [-1 for i in range(N)]
parent[0] = 0

q = collections.deque()
q.append(0)

point = [0 for i in range(N)]

for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    point[p] += x

while(q):
    x = q.popleft()
    for y in g[x]:
        if parent[y] == -1:
            q.append(y)
            parent[y] = x
            point[y] += point[x]

print(" ".join(map(str, point)))
### BUGGY CODE ###

import fractions
K = int(input())
sum = 0
for a in range(1,K+1,1):
    for b in range(1,K+1,1):
        for c in range(1,K+1,1):
            sum+=fractions.gcd(c,fractions.gcd(a,b))
print(sum)

### FIXED CODE ###

import math
K = int(input())
sum = 0
for a in range(1,K+1,1):
    for b in range(1,K+1,1):
        tmp = math.gcd(a,b)
        for c in range(1,K+1,1):
            sum+=math.gcd(c,tmp)
print(sum)
### BUGGY CODE ###

from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/agc033/tasks/agc033_b
# B - LRUD Game
"""
"""
H = gi()
W = gi()
N = gi()
sr = gi()
sc = gi()
S = gw()
T = gw()
d_to_i = {"L": 0, "R": 1, "U": 2, "D": 3}
cnt = [[0 for x in range(4)] for i in range(2)]


def o(pos, si, ti, d, sb, tb):
    for i in range(N):
        if (d_to_i[S[i]] == si):
            pos += d
            if pos == sb:
                return 1
        if (d_to_i[T[i]] == ti):
            if (pos - d != tb):
                pos -= d
    return 0


off = 0
for i in range(N):
    #  print(cnt)
    off = o(sc, 0, 1, -1, 0, W + 1)
    off = off or o(sc, 1, 0, 1, W + 1, 0)
    off = off or o(sr, 2, 3, -1, 0, H + 1)
    off = off or o(sr, 3, 2, 1, H + 1, 0)

if off:
    print("NO")
else:
    print("YES")


### FIXED CODE ###

from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/agc033/tasks/agc033_b
# B - LRUD Game
"""
"""
H = gi()
W = gi()
N = gi()
sr = gi()
sc = gi()
S = gw()
T = gw()
d_to_i = {"L": 0, "R": 1, "U": 2, "D": 3}
cnt = [[0 for x in range(4)] for i in range(2)]


def o(pos, si, ti, d, sb, tb):
    for i in range(N):
        if (d_to_i[S[i]] == si):
            pos += d
            if pos == sb:
                return 1
        if (d_to_i[T[i]] == ti):
            if (pos - d != tb):
                pos -= d
    return 0


off = 0
#  print(cnt)
off = o(sc, 0, 1, -1, 0, W + 1)
off = off or o(sc, 1, 0, 1, W + 1, 0)
off = off or o(sr, 2, 3, -1, 0, H + 1)
off = off or o(sr, 3, 2, 1, H + 1, 0)

if off:
    print("NO")
else:
    print("YES")