CodeEff/ECCO huggingface dataset:
# Original solution
n = int(eval(input()))
nxt_btn = {i: int(eval(input())) for i in range(1, n + 1)}

num = 0
crr_btn = 1
while True:
    num += 1
    if nxt_btn[crr_btn] == 1:
        num = -1
        break
    if nxt_btn[crr_btn] == 2:
        break
    crr_btn = nxt_btn[crr_btn]
print(num)


# Optimized solution
n = int(eval(input()))
nxt_btn = {i: int(eval(input())) for i in range(1, n + 1)}

num = -1
crr_btn = 1
for i in range(1, n + 1):
    if nxt_btn[crr_btn] == 2:
        num = i
        break
    crr_btn = nxt_btn[crr_btn]
print(num)
# Original solution
n = int(eval(input()))
a = [int(eval(input())) for i in range(n)]
i = a[0]
num = [1, i]
for k in range(n):
    if 2 in num:
        print((len(num) - 1))
        break
    j = a[i-1]
    if j in num:
        print((-1))
        break
    num.append(j)
    if 2 in num:
        print((len(num) - 1))
        break
    i = a[j-1]
    if i in num:
        print((-1))
        break
    num.append(i)

# Optimized solution
n = int(eval(input()))
a = [int(eval(input())) for i in range(n)]
i = a[0]
for j in range(n):
    if i == 2:
        print((j + 1))
        break
    i = a[i-1]
else:
	print((-1))
# Original solution
N = int(eval(input()))
A = [0]
for i in range(N):
    a = int(eval(input()))
    A.append(a)
ans = 1
now = A[1]
while now != 1 and now != 2:
    ans += 1
    now = A[now]
if now == 1:
    print((-1))
else:
    print(ans)

# Optimized solution
N = int(eval(input()))
A = [0]
for i in range(N):
    a = int(eval(input()))
    A.append(a)
#print(A)
ans = 1
now = A[1]
visited = {}
while (not now in visited) and now != 2:
    ans += 1
    visited[now] = 1
    now = A[now]
#print(visited)
if now != 2:
    print((-1))
else:
    print(ans)
# Original solution
n=int(eval(input()))
Alist=[0]+[int(eval(input())) for i in range(n)]

now=1
count=0
Hist=[1]

while now!=2:
    now=Alist[now]
    count+=1
    if now in Hist:
        count=-1
        break
    Hist.append(now)
print(count)

# Optimized solution
n=int(eval(input()))
Alist=[0]+[int(eval(input())) for i in range(n)]

now=1
count=0

for _ in range(n):
    now=Alist[now]
    count+=1
    if now==2:
        print(count)
        exit()
print((-1))
# Original solution
n=int(eval(input()))
Alist=[0]+[int(eval(input())) for i in range(n)]

now=1
Hist=[1]

for i in range(n):
    now=Alist[now]
    if now==2:
        print((i+1))
        break
    if now in Hist:
        print((-1))
        break
    Hist.append(now)

# Optimized solution
n=int(eval(input()))
Alist=[0]+[int(eval(input())) for i in range(n)]

now=1
Hist={1}

for i in range(n):
    now=Alist[now]
    if now==2:
        print((i+1))
        break
    if now in Hist:
        print((-1))
        break
    Hist.add(now)
# Original solution
# https://beta.atcoder.jp/contests/abc065/tasks/abc065_b

import sys


def model():
    e = list(map(int, sys.stdin))
    cur = e[1]
    for i in range(e[0]):
        if cur == 2:
            print((i + 1))
            break
        cur = e[cur]
    else:
        print((-1))


def input_lines():
    """hell?"""
    lines = sys.stdin.readlines()
    for i in range(1, int(lines[0])+1):
        yield i, int(lines[i].strip())


def solve():
    d = {i: button for i, button in input_lines()}
    count = 1
    index = 1

    while True:
        try:
            prev = index
            index = d[index]

            if index == 2:
                print(count)
                exit()
            elif index is None:
                print((-1))
                exit()
            d[prev] = None
            count += 1
        except KeyError:
            print((-1))
            exit()


if __name__ == '__main__':
    solve()
    # model()


# Optimized solution
# https://beta.atcoder.jp/contests/abc065/tasks/abc065_b

import sys


def model():
    e = list(map(int, sys.stdin))
    cur = e[1]
    for i in range(e[0]):
        if cur == 2:
            print((i + 1))
            break
        cur = e[cur]
    else:
        print((-1))


def input_lines():
    """hell?"""
    lines = sys.stdin.readlines()
    for i in range(1, int(lines[0])+1):
        yield i, int(lines[i].strip())


def solve():
    d = {i: button for i, button in input_lines()}
    count = 1
    index = 1

    while True:
        try:
            prev = index
            index = d[index]

            if index is None:
                print((-1))
                exit()
            elif index == 2:
                print(count)
                exit()
            d[prev] = None
            count += 1
        except KeyError:
            print((-1))
            exit()


if __name__ == '__main__':
    solve()
    # model()
# Original solution
n=int(eval(input()))
a=[]
for i in range(n):
    a.append(int(eval(input()))-1)
'''
#TLEチーンコ
i=0
j=0
b=[]
while True:
    j+=1
    if a[i]==1:
        print(j)
        break
    elif a[i] in b:
        print(-1)
        break
    else:
        b.append(a[i])
        i=a[i]
'''
i=0
j=0
while True:
    j+=1
    if a[i]==1:
        print(j)
        break
    elif j==n:
        print((-1))
        break
    else:
        i=a[i]


# Optimized solution
n=int(eval(input()))
a=[int(eval(input()))-1 for i in range(n)]
now=0
x=[0]*n
i=0
while x[now]==0:
    i+=1
    x[now]=1
    now=a[now]
    if now==1:
        print(i)
        break
else:
    print((-1))
# Original solution
n = int(eval(input()))
a = []
l = [0]*(n + 1)
cnt = 0
now = 1

for i in range(n):
    a.append(int(eval(input())))

for i in range(n):
    cnt += 1
    now = a[now - 1]
    if now == 2:
        print(cnt)
        exit()

print((-1))

# Optimized solution
import sys
input = sys.stdin.readline

def main():
    n = int(eval(input()))
    a = []
    l = [0]*(n + 1)
    cnt = 0
    now = 1

    for i in range(n):
        a.append(int(eval(input())))

    for i in range(n):
        cnt += 1
        now = a[now - 1]
        if now == 2:
            print(cnt)
            exit()
    print((-1))

main()
# Original solution
import sys
input = sys.stdin.readline

def main():
    n = int(eval(input()))
    a = []
    l = [0]*(n + 1)
    cnt = 0
    now = 1

    for i in range(n):
        a.append(int(eval(input())))

    for i in range(n):
        cnt += 1
        now = a[now - 1]
        if now == 2:
            print(cnt)
            exit()
    print((-1))

main()

# Optimized solution
import sys
input = sys.stdin.readline

def main():
    n = int(eval(input()))
    a = []
    l = [0]*(n + 1)
    now = 0

    for i in range(n):
        a.append(int(eval(input())) - 1)

    for i in range(n):
        now = a[now]
        if now == 1:
            print((i + 1))
            exit()
    print((-1))

main()
# Original solution
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    N=int(eval(input()))

    A=[int(eval(input())) for i in range(N)]
    temp=[0]*N
    i = 0
    cnt=0

    while True:
        if A[i] not in temp:
            temp[cnt] = A[i]
            if A[i]==2:
                print((cnt+1))
                break
            i=A[i]-1
            cnt+=1

        else:
            print((-1))
            break
resolve()

# Optimized solution
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    N=int(eval(input()))

    A=[int(eval(input())) for i in range(N)]
    num=0
    cnt=0

    for i in range(N):
        if A[num]==2:
            print((cnt+1))
            break
        num=A[num]-1
        cnt+=1

        if i==N-1:
            print((-1))

resolve()
# Original solution
#/usr/bin/env python

n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]

lighted = [0] 
ans = 0 

while True:
    u = lighted[-1]
    v = a[u]-1
    ans += 1
    if v == 1:
        print(ans)
        exit()
    if v not in lighted:
        lighted.append(v)
    else:
        print((-1))
        exit()


# Optimized solution
#/usr/bin/env python

n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]

lighted = [0] 
ans = 0 

for i in range(n):
    u = lighted[-1]
    v = a[u]-1
    ans += 1
    if v == 1:
        print(ans)
        exit()
    lighted.append(v)

print((-1))
# Original solution
#/usr/bin/env python

n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]

lighted = [0] 
ans = 0 

for i in range(n):
    u = lighted[-1]
    v = a[u]-1
    ans += 1
    if v == 1:
        print(ans)
        exit()
    lighted.append(v)

print((-1))


# Optimized solution
#/usr/bin/env python

n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]

ans = 0 
v = 0 
for i in range(n):
    v = a[v]-1
    ans += 1
    if v == 1:
        print(ans)
        exit()

print((-1))
# Original solution

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

# スコア行列[K, K]
# 白チェッカー左下を(x, y)としたときの正解数-誤答数
score_matrix = [[0 for x in range(K+1)] for y in range(K+1)]
base_hope = 0

for i in range(N):
    x, y, c = input().split()
    x2, y2 = int(x) // K, int(y) // K
    x_coord, y_coord = int(x) % K, int(y) % K
    # 正解
    if ((x2 + y2) % 2 == 0 and c == "W") or ((x2 + y2) % 2 == 1 and c == "B"):
        score_matrix[y_coord+1][x_coord+1] += 1
        base_hope += 1
    # 誤答
    else:
        score_matrix[y_coord+1][x_coord+1] -= 1

# スコア行列の二次元累積和を求める O(K^2)
xy = [(x, y) for x in range(1, K+1) for y in range(1, K+1)]
for x, y in xy:
    score_matrix[y][x] += score_matrix[y][x-1] + score_matrix[y-1][x] - score_matrix[y-1][x-1]

# 希望行列を累積和に基づき計算していく O(K^2)
# 同時に最大値を計算
max_hope = 0
for x, y in xy:
    hope = base_hope - score_matrix[K][x-1] - score_matrix[y-1][K] + 2 * score_matrix[y-1][x-1]
    true_hope = max(hope, N - hope)
    if true_hope > max_hope:
        max_hope = true_hope

print(max_hope)


# Optimized solution
N, K = list(map(int, input().split()))

score = [[0 for x in range(K+1)] for y in range(K+1)]
base_hope = 0

for i in range(N):
    x, y, c = input().split()
    x2, y2 = int(x) // K, int(y) // K
    x_coord, y_coord = int(x) % K + 1, int(y) % K + 1
    if ((x2 + y2) % 2 == 0 and c == "W") or ((x2 + y2) % 2 == 1 and c == "B"):
        score[y_coord][x_coord] += 1
        base_hope += 1
    else:
        score[y_coord][x_coord] -= 1

xy = [(x, y) for x in range(K) for y in range(K)]
for x, y in xy:
    score[y+1][x+1] += score[y+1][x] + score[y][x+1] - score[y][x]

max_hope = 0
for x, y in xy:
    hope = base_hope - score[K][x] - score[y][K] + 2 * score[y][x]
    true_hope = max(hope, N - hope)
    if true_hope > max_hope:
        max_hope = true_hope

print(max_hope)
# Original solution
N, K = list(map(int, input().split()))

score = [[0 for x in range(K+1)] for y in range(K+1)]
base_hope = 0

for i in range(N):
    x, y, c = input().split()
    x2, y2 = int(x) // K, int(y) // K
    x_coord, y_coord = int(x) % K + 1, int(y) % K + 1
    if ((x2 + y2) % 2 == 0 and c == "W") or ((x2 + y2) % 2 == 1 and c == "B"):
        score[y_coord][x_coord] += 1
        base_hope += 1
    else:
        score[y_coord][x_coord] -= 1

xy = [(x, y) for x in range(K) for y in range(K)]
for x, y in xy:
    score[y+1][x+1] += score[y+1][x] + score[y][x+1] - score[y][x]

max_hope = 0
for x, y in xy:
    hope = base_hope - score[K][x] - score[y][K] + 2 * score[y][x]
    true_hope = max(hope, N - hope)
    if true_hope > max_hope:
        max_hope = true_hope

print(max_hope)

# Optimized solution
N, K = list(map(int, input().split()))

score = [[0] * (K+1) for y in range(K+1)]
base_hope = 0

for i in range(N):
    x, y, c = input().split()
    x2, y2 = int(x) // K, int(y) // K
    x_coord, y_coord = int(x) % K + 1, int(y) % K + 1
    if ((x2 + y2) % 2 == 0 and c == "W") or ((x2 + y2) % 2 == 1 and c == "B"):
        score[y_coord][x_coord] += 1
        base_hope += 1
    else:
        score[y_coord][x_coord] -= 1

xy = [(x, y) for x in range(K) for y in range(K)]
for x, y in xy:
    score[y+1][x+1] += score[y+1][x] + score[y][x+1] - score[y][x]

max_hope = 0
for x, y in xy:
    hope = base_hope - score[K][x] - score[y][K] + 2 * score[y][x]
    true_hope = hope if hope > N - hope else N - hope
    if true_hope > max_hope:
        max_hope = true_hope

print(max_hope)
# Original solution
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N = na[0]
    K = na[1]
    x = []
    y = []
    c = []
    for i in range(N):
        sa = input().split()
        x.append(int(sa[0]))
        y.append(int(sa[1]))
        c.append(True if sa[2] == 'W' else False)

    hopes = [[0 for j in range(K * 2)] for i in range(K * 3)]
    xsum = [0 for j in range(K * 2)]
    ysum = [[0 for j in range(K * 2)] for i in range(K * 3)]

    for i in range(N):
        if c[i]:
            x[i] += K
        xmod = x[i] % (K * 2)
        ymod = y[i] % (K * 2)
        if K <= xmod and K <= ymod:
            xmod -= K
            ymod -= K
        elif K <= ymod:
            xmod += K
            ymod -= K

        hopes[xmod][ymod] += 1
        if xmod < K:
            hopes[xmod + K][ymod + K] += 1
            hopes[xmod + K * 2][ymod] += 1
        else:
            hopes[xmod - K][ymod + K] += 1
            hopes[xmod + K][ymod + K] += 1

    for j in range(K * 2):
        for i in range(K):
            xsum[j] += hopes[i][j]
    for i in range(K):
        ysum[i][0] = ysum[i + K * 2][0] = s = sum(hopes[i][:K])
        for j in range(1, K):
            s += (hopes[i][j + K - 1] - hopes[i][j - 1])
            ysum[i][j] = ysum[i + K * 2][j] = s
    for i in range(K, K * 2):
        ysum[i][0] = s = sum(hopes[i][:K])
        for j in range(1, K):
            s += (hopes[i][j + K - 1] - hopes[i][j - 1])
            ysum[i][j] = s

    h0 = []
    hmax = h = sum(xsum[:K])
    h0.append(h)
    for j in range(1, K):
        h += (xsum[j + K - 1] - xsum[j - 1])
        hmax = max(hmax, h)
        h0.append(h)
    for j in range(K):
        h = h0[j]
        for i in range(1, K * 2):
            h += (ysum[i + K - 1][j] - ysum[i - 1][j])
            hmax = max(hmax, h)

    print(hmax)


if __name__ == '__main__':
    main()



# Optimized solution
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N = na[0]
    K = na[1]
    x = []
    y = []
    c = []
    for i in range(N):
        sa = input().split()
        x.append(int(sa[0]))
        y.append(int(sa[1]))
        c.append(True if sa[2] == 'W' else False)

    hopes = [[0 for j in range(K)] for i in range(K)]
    ysum = [[0 for j in range(K * 2)] for i in range(K)]

    score = 0
    for i in range(N):
        xmod = x[i] % K
        ymod = y[i] % K
        f = (int(x[i] / K) + int(y[i] / K)) % 2 == 1
        c[i] ^= f
        if c[i]:
            score += 1
        h = -1 if c[i] else 1
        hopes[xmod][ymod] += h

    for i in range(K):
        s = 0
        for j in range(K):
            s += hopes[i][j]
            ysum[i][j] = s
        for j in range(K):
            s -= hopes[i][j]
            ysum[i][K + j] = s

    smax = 0
    for j in range(K):
        s = 0
        for i in range(K):
            s += ysum[i][K + j]
        for i in range(K):
            s += (ysum[i][j] - ysum[i][K + j])
            smax = max(smax, s)
        for i in range(K):
            s -= (ysum[i][j] - ysum[i][K + j])
            smax = max(smax, s)

    print((score + smax))


if __name__ == '__main__':
    main()
# Original solution
n, k = list(map(int, input().split()))
mp1 = [[0] * k for _ in range(k)]
mp2 = [[0] * k for _ in range(k)]
for _ in range(n):
  x, y, c = input().split()
  t = int(x) // k + int(y) // k
  x = int(x) % k
  y = int(y) % k
  if c == "B":
    t += 1
  if t % 2:
    mp1[y][x] += 1
  else:
    mp2[y][x] += 1

for x in range(1, k):
  mp1[0][x] += mp1[0][x - 1]
  mp2[0][x] += mp2[0][x - 1]

for y in range(1, k):
  acc1 = 0
  acc2 = 0
  for x in range(k):
    acc1 += mp1[y][x]
    mp1[y][x] = acc1 + mp1[y - 1][x]
    acc2 += mp2[y][x]
    mp2[y][x] = acc2 + mp2[y - 1][x]

ans = 0
sum1 = mp1[k - 1][k - 1]
sum2 = mp2[k - 1][k - 1]
mp1k = mp1[k - 1]
mp2k = mp2[k - 1]
for y in range(k):
  mp1y = mp1[y]
  mp1yk = mp1y[k - 1]
  mp2y = mp2[y]
  mp2yk = mp2y[k - 1]
  for x in range(k):
    mp1yx = mp1y[x]
    mp2yx = mp2y[x]
    mp1kx = mp1k[x]
    mp2kx = mp2k[x]

    ans = max(ans, 2 * mp1yx + sum1 - mp1yk - mp1kx + mp2kx + mp2yk - 2 * mp2yx)
    ans = max(ans, 2 * mp2yx + sum2 - mp2yk - mp2kx + mp1kx + mp1yk - 2 * mp1yx)

print(ans)

# Optimized solution
def main():
  n, k = list(map(int, input().split()))
  mp1 = [[0] * k for _ in range(k)]
  mp2 = [[0] * k for _ in range(k)]
  for _ in range(n):
    x, y, c = input().split()
    t = int(x) // k + int(y) // k
    x = int(x) % k
    y = int(y) % k
    if c == "B":
      t += 1
    if t % 2:
      mp1[y][x] += 1
    else:
      mp2[y][x] += 1
  
  mp10 = mp1[0]
  mp20 = mp2[0]
  for x in range(1, k):
    mp10[x] += mp10[x - 1]
    mp20[x] += mp20[x - 1]
  
  for y in range(1, k):
    acc1 = 0
    acc2 = 0
    mp1y = mp1[y]
    mp2y = mp2[y]
    mp1y1 = mp1[y - 1]
    mp2y1 = mp2[y - 1]
    for x in range(k):
      acc1 += mp1y[x]
      mp1y[x] = acc1 + mp1y1[x]
      acc2 += mp2y[x]
      mp2y[x] = acc2 + mp2y1[x]
  
  ans = 0
  sum1 = mp1[k - 1][k - 1]
  sum2 = mp2[k - 1][k - 1]
  mp1k = mp1[k - 1]
  mp2k = mp2[k - 1]
  for y in range(k):
    mp1y = mp1[y]
    mp1yk = mp1y[k - 1]
    mp2y = mp2[y]
    mp2yk = mp2y[k - 1]
    for x in range(k):
      mp1yx = mp1y[x]
      mp2yx = mp2y[x]
      mp1kx = mp1k[x]
      mp2kx = mp2k[x]
  
      a1 = 2 * mp1yx + sum1 - mp1yk - mp1kx + mp2kx + mp2yk - 2 * mp2yx
      a2 = 2 * mp2yx + sum2 - mp2yk - mp2kx + mp1kx + mp1yk - 2 * mp1yx
  
      if ans < a1:
        ans = a1
      if ans < a2:
        ans = a2
  
  
  print(ans)

main()
# Original solution
n,k=list(map(int,input().split()))
grid=[[0]*k for _ in range(k)]
for i in range(n):
    x,y,c=[x for x in input().split()]
    x,y=int(x),int(y)
    p=(x//k+y//k)%2
    if (p==0 and c=="B")|(p==1 and c=="W"): grid[x%k][y%k]+=1
    else: grid[x%k][y%k]-=1

for i in range(k):
    for j in range(1,k):
        grid[i][j]+=grid[i][j-1]

for i in range(1,k):
    for j in range(k):
        grid[i][j]+=grid[i-1][j]


ans=0
for i in range(k):
    for j in range(k):
        b=grid[i][j]*4+grid[k-1][k-1]-(grid[i][k-1]+grid[k-1][j])*2
        ans=max(ans,(n+b)//2,(n-b)//2)
print(ans)

# Optimized solution
n,k=list(map(int,input().split()))
grid=[[0]*k for _ in range(k)]
for i in range(n):
    x,y,c=[x for x in input().split()]
    x,y=int(x),int(y)
    p=(x//k+y//k)%2
    if (p==0 and c=="B")|(p==1 and c=="W"): grid[x%k][y%k]+=1
    else: grid[x%k][y%k]-=1

for i in range(k):
    for j in range(1,k):
        grid[i][j]+=grid[i][j-1]

for i in range(1,k):
    for j in range(k):
        grid[i][j]+=grid[i-1][j]


ans=0
for i in range(k):
    for j in range(k):
        b=grid[i][j]*4+grid[k-1][k-1]-(grid[i][k-1]+grid[k-1][j])*2
        ans=max(ans,n+b,n-b)
print((ans//2))
# Original solution
n,k=list(map(int,input().split()))
grid=[[0]*k for _ in range(k)]
for i in range(n):
    x,y,c=[x for x in input().split()]
    x,y=int(x),int(y)
    p=(x//k+y//k)%2
    if (p==0 and c=="B")|(p==1 and c=="W"): grid[x%k][y%k]+=1
    else: grid[x%k][y%k]-=1

for i in range(k):
    for j in range(1,k):
        grid[i][j]+=grid[i][j-1]

for i in range(1,k):
    for j in range(k):
        grid[i][j]+=grid[i-1][j]


ans=0
for i in range(k):
    for j in range(k):
        b=grid[i][j]*4+grid[k-1][k-1]-(grid[i][k-1]+grid[k-1][j])*2
        ans=max(ans,n+b,n-b)
print((ans//2))

# Optimized solution
def main():
    n,k=list(map(int,input().split()))
    grid=[[0]*k for _ in range(k)]
    for i in range(n):
        x,y,c=[x for x in input().split()]
        x,y=int(x),int(y)
        p=(x//k+y//k)%2
        if (p==0 and c=="B")|(p==1 and c=="W"): grid[x%k][y%k]+=1
        else: grid[x%k][y%k]-=1

    for i in range(k):
        for j in range(1,k):
            grid[i][j]+=grid[i][j-1]

    for i in range(1,k):
        for j in range(k):
            grid[i][j]+=grid[i-1][j]


    ans=0
    for i in range(k):
        for j in range(k):
            b=grid[i][j]*4+grid[k-1][k-1]-(grid[i][k-1]+grid[k-1][j])*2
            ans=max(ans,n+b,n-b)
    print((ans//2))

if __name__ == "__main__":
    main()
# Original solution
n,k=list(map(int,input().split()))
a=[(2*k+1)*[0]for _ in range(2*k+1)]
for _ in range(n):
  x,y,c=input().split()
  x=int(x)
  y=int(y)
  if c=="B":y+=k
  x%=2*k
  y%=2*k
  a[x+1][y+1]+=1
ans=0
for i in range(1,2*k+1):
  for j in range(1,2*k+1):a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]
for i in range(k,2*k+1):
  for j in range(k,2*k+1):
    t=a[i][j]-a[i-k][j]-a[i][j-k]+a[i-k][j-k]
    t+=a[i-k][j-k]
    t+=a[2*k][j-k]-a[i][j-k]
    t+=a[i-k][2*k]-a[i-k][j]
    t+=a[2*k][2*k]-a[i][2*k]-a[2*k][j]+a[i][j]
    ans=max(ans,t,n-t)
print(ans)

# Optimized solution
n,k=list(map(int,input().split()));m=2*k;a=[(m+1)*[0]for _ in[0]*(m+1)];z=lambda i,j:(a[i][j]-a[i-k][j]-a[i][j-k]+a[i-k][j-k])*2+a[m][m]-a[i][m]-a[m][j]+a[i-k][m]+a[m][j-k]
for _ in[0]*n:x,y,c=input().split();x=int(x);y=int(y)+k*(c=="B");a[x%m+1][y%m+1]+=1
for i in range(m):
  for j in range(m):a[i+1][j+1]+=a[i][j+1]+a[i+1][j]-a[i][j]
print((max(max(max(z(i,j),n-z(i,j))for j in range(k,m+1))for i in range(k,m+1))))
# Original solution
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()

W = [[0 for _ in range(2*K+3)] for _ in range(2*K+3)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[0][y+K+1] -= 1
        W[x+1][0] += 1
        W[x+1][y+1] -= 2
        W[x+1][y+K+1] += 2
        W[x+1][2*K] -= 1
        W[x+K+1][0] -= 1
        W[x+K+1][y+1] += 2
        W[x+K+1][y+K+1] -= 2
        W[x+K+1][2*K] += 1
        W[2*K][y+1] -= 1
        W[2*K][y+K+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[x+K+1][y+1] -= 2
        W[x+1][y+K+1] -= 2
        W[x+K+1][y+K+1] += 1
        W[x+K+1][0] += 1
        W[2*K][0] -= 1
        W[2*K][y+1] += 1
        W[0][y+K+1] += 1
        W[0][2*K] -= 1
        W[x+1][2*K] += 1

ans = 0
for x in range(0,2*K+1):
    for y in range(0,2*K+1):
        W[x][y] += W[x][y-1]
for y in range(0,2*K+1):
    for x in range(0,2*K+1):
        W[x][y] += W[x-1][y]
        ans = max(ans,W[x][y])

print(ans)


# Optimized solution
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18
 
N,K=rl()
 
W = [[0 for _ in range(K+3)] for _ in range(K+3)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[x+1][y+1] -= 2
        W[0][K+1] -= 1
        W[x+1][K+1] += 1
        W[x+1][0] += 1
        W[K+1][0] -= 1
        W[K+1][y+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[K+1][y+1] -= 1
        W[x+1][K+1] -= 1
        W[K+1][K+1] += 1
 
for x in range(0,K+2):
    for y in range(0,K+2):
        W[x][y] += W[x][y-1]
for y in range(0,K+2):
    for x in range(0,K+2):
        W[x][y] += W[x-1][y]
 
ans = 0
for x in range(K+1):
    for y in range(K+1):
        res = W[x][y]
        ans = max(ans,res,N-res)
 
print(ans)