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

s = input()
total = 0

while '01' in s or '10' in s:
  total += s.count('01') * 2
  s = s.replace('01', '')
  total += s.count('10') * 2
  s = s.replace('10', '')

print(total)


### FIXED CODE ###

s = input()
total = 0

count_0 = s.count('0') * 2
count_1 = s.count('1') * 2

if count_0 < count_1:
  print(count_0)
else:
  print(count_1)
### BUGGY CODE ###

def main():
    import sys
    from collections import Counter
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    Q = int(sys.stdin.readline())
    BC = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    C = Counter(A)
    '''
    L = [0 for _ in range(10**5+1)]
    for key, value in C.items():
        L[key] = value
    '''
        
        
    for bc in BC:
        C[bc[1]] += C[bc[0]]
        C[bc[0]]= 0
        ans = 0
        for key, value in C.items():
            ans += key*value
        print(ans)
        



if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import Counter
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    Q = int(sys.stdin.readline())
    BC = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    C = Counter(A)
    '''
    L = [0 for _ in range(10**5+1)]
    for key, value in C.items():
        L[key] = value
    '''
        
    ans = 0
    for bc in BC:
        C[bc[1]] += C[bc[0]]
        tmp = C[bc[0]]
        C[bc[0]]= 0
        #print(C)
        if ans == 0:
            for key, value in C.items():
                ans += key*value
        else:
            ans +=(bc[1]-bc[0])*tmp
        print(ans)
        



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

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [0]*M
mod = 10**9+7

for i in range(M):
    a[i] = int(input())

DP = [0]*(N+1)
DP[0] = 1
if 1 in a:
    DP[1] = 0
else:
    DP[1] = 1

for i in range(2, N+1):
    if(i not in a):
        DP[i] = (DP[i-1]+DP[i-2])%mod
        
print(DP[N])

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [0]*M
mod = 10**9+7

for i in range(M):
    a[i] = int(input())

a = set(a)
DP = [0]*(N+1)
DP[0] = 1
if 1 in a:
    DP[1] = 0
else:
    DP[1] = 1

for i in range(2, N+1):
    if(i not in a):
        DP[i] = (DP[i-1]+DP[i-2])%mod
        
print(DP[-1])
### BUGGY CODE ###

def start_point(n, k, P):
    mx, total, x = 0, 0, 0
    for i in range(n - k + 1):
        for j in range(i, i + k):
            total += expected_value(P[j])
        mx = max(mx, total)
        if mx == total:
            x = i
        total = 0
    return x

def expected_value(p):
    value = 0
    for i in range(p + 1):
        value += i
    return value / p

def main():

    n, k = map(int, input().split())
    P = list(map(int, input().split()))
    ans = 0
    start = start_point(n, k, P)
    for i in range(start, start + k):
        ans += expected_value(P[i])
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():

    n, k = map(int, input().split())
    P = list(map(int, input().split()))
    # print(exp_sum(n, k, P))
    mx = 0
    for i in range(k):
        mx += (P[i] + 1) / 2
    tmp = mx
    for i in range(k, n):
        tmp += (P[i] - P[i - k]) / 2
        mx = max(mx, tmp)
    print(mx)

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

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

sum = 1
for i in range(n):
  sum = sum * int(a[i])

c = 1

for k in range(18):
  c = c * 10

if sum > c :
  print(-1)
else:
  print(sum)

### FIXED CODE ###

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

sum = 1
for i in a:
  sum = sum * int(i)
  if sum > 1000000000000000000:
    break

if "0" in a:
  print(0)
elif sum > 1000000000000000000:
  print(-1)
else:
  print(sum)
### BUGGY CODE ###

K,S=map(int, input().split())
cnt=0
for i in range(K+1):
  X=i
  for j in range(K+1):
    Y=j
    if S-(X+Y)in range(K+1):
      cnt+=1
print(cnt)

### FIXED CODE ###

K,S=map(int, input().split())
cnt=0
if K <= S:
  for i in range(K+1):
    for j in range(K+1):
      if S - (i+j) <= K and S >= i+j:
        cnt += 1
else:
  for i in range(S+1):
    for j in range(S+1):
      if S - (i+j) <= K and S >= i+j:
        cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
s = str(input())
count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i] and j -i != k-j:
                count += 1
print(count)

### FIXED CODE ###

n = int(input())
s = str(input())
r = s.count("R")
g = s.count("G")
b = s.count("B")
total = r * g * b
for i in range(2000):
    for j in range(n-2*i):
        if j + (2*i) <= n-1:
            if s[j] != s[j+i] and s[j+i] != s[j+(2*i)] and s[j+(2*i)] != s[j]:
                total -= 1
print(total)
### BUGGY CODE ###

import math


def combinations_with_replacement_count(n, r):
    return math.factorial(n + r - 1) // (math.factorial(n - 1) * math.factorial(r))


nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
fact = {}
i = 2
while i * i <= m:
    while m % i == 0:
        m = m // i
        if i in fact:
            fact[i] += 1
        else:
            fact[i] = 1
    i += 1
if m > 1:
    fact[m] = 1
j = 2
ans = 1
for k in fact:
    ans = ans * combinations_with_replacement_count(n, fact[k])
print(ans % (10 ** 9 + 7))


### FIXED CODE ###

import math


def combinations_with_replacement_count(n, r):
    return math.factorial(n + r - 1) // (math.factorial(n - 1) * math.factorial(r))


nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
fact = {}
i = 2
while i * i <= m:
    while m % i == 0:
        m = m // i
        if i in fact:
            fact[i] += 1
        else:
            fact[i] = 1
    i += 1
if m > 1:
    fact[m] = 1
j = 2
ans = 1
for k in fact:
    ans = ans * combinations_with_replacement_count(n, fact[k])
print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

N,Q = map(int,input().split())
line = list(input())
AC_locate = []
count_s = []
for i in range(N-1):
    if line[i] == 'A' and line[i+1] == 'C':
        AC_locate.append(int(i))
for i in range(Q):
    l,r = map(int,input().split())
    count = 0
    for locate in AC_locate:
        if locate > r-2:
            break
        if locate > l-2:
            count += 1
    # for i in range(l-1,r):
    #     if line[i] == 'A' and line[i+1] == 'C':
    #         count += 1
    print(count)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
AC_cnt = [0] * N
for i in range(N-1):
  if S[i] == 'A' and  S[i+1] == 'C':
    AC_cnt[i+1] = AC_cnt[i] + 1
  else:
    AC_cnt[i+1] = AC_cnt[i]

for i in range(Q):
  begin, end = map(int,input().split())
  print(AC_cnt[end-1]-AC_cnt[begin-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

class Event:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

    for i in range(q):
        d = int(input())

        # ユーザ評価イベント
        e = Event()
        e.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        e.type = 0 # evaluate
        e.pos = None
        e.idx = i
        l_event.append(e)

    # リストを時刻でソート O((N+Q)log(N+Q))
    l_event = sorted(l_event, key=lambda e: e.time)

    ans = [-1]*q # 答えの配列
    s_stop = set()

    # リストを順に処理する
    for e in l_event: #O(N+Q)
        if e.type == 1: # add
            s_stop.add(e.pos)
        elif e.type == -1: # delete
            s_stop.remove(e.pos)
        else: #evaluate
            if len(s_stop) != 0:
                ans[e.idx] = min(s_stop) # O(logN)
            else:
                pass

    print("\n".join([str(a) for a in ans]))

solve()

### FIXED CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

N = int(input())
S_list = []
for _ in range(N):
    S_list.append(input())

str_list = set(S_list)
str_count_dict = {}
for val in str_list:
    str_count_dict[val] = S_list.count(val)

max_key = sorted([key for key, val in str_count_dict.items()\
                  if val == max(str_count_dict.values())])

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

### FIXED CODE ###

N = int(input())
S_list = [input() for i in range(N)]
 
S_count = {}
for Si in S_list:
    if Si in S_count:
        S_count[Si] += 1
    else:
        S_count[Si] = 1

S_max = max(S_count.values())
S_count_sorted = sorted([key for key, val in S_count.items()\
                  if val == S_max])
 
print('\n'.join(S_count_sorted))
### BUGGY CODE ###

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1, N+1):
    for j in range(0, W+1):
        if j >= w[i-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1])
        dp[i][j] = max(dp[i][j], dp[i-1][j])

print(dp[N][W])

### FIXED CODE ###

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

dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(0, W+1):
        if j >= w:
            dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v)
        dp[i][j] = max(dp[i][j], dp[i-1][j])

print(dp[N][W])
### BUGGY CODE ###

from collections import Counter
def main():
    S = input()
    A = [0] * ((n := len(S)) + 1)
    A[1] = (a := int(S[-1])) % 2019
    for i in range(2, n + 1):
        a += pow(10, i - 1) * int(S[-i])
        A[i] = a % 2019
    c = Counter(A)
    ans = 0
    for v in c.values():
        ans += v * (v - 1) // 2
    print(ans)
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter
def main():
    S = input()
    A = [0] * ((n := len(S)) + 1)
    A[1] = (a := int(S[-1])) % 2019
    for i in range(2, n + 1):
        a += pow(10, i - 1, 2019) * int(S[-i])
        A[i] = a % 2019
    c = Counter(A)
    ans = 0
    for v in c.values():
        ans += v * (v - 1) // 2
    print(ans)

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

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n=int(input())
a=list(map(int,input().split()))
cnt={}
comb={}
ans=0
for i in a:
    if i in cnt:
        cnt[i]+=1
    else:
        cnt[i]=1
        
for i in cnt.values():
    if i<2:
        continue
    if not i in comb:
        comb[i]=combinations_count(i,2)
    ans+=comb[i]

for i in range(n):
    pans=ans
    if cnt[a[i]] in comb:
        pans-=comb[cnt[a[i]]]
    c=cnt[a[i]]-1
    if c>1:
        if c in comb:
            pans+=comb[c]
        else:
            pans+=combinations_count(c,2)
    print(pans)



### FIXED CODE ###

import math

def combinations_count(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n=int(input())
a=list(map(int,input().split()))
cnt={}
comb={}
ans=0
for i in a:
    if i in cnt:
        cnt[i]+=1
    else:
        cnt[i]=1
        
for i in cnt.values():
    if i<2:
        continue
    if not i in comb:
        comb[i]=combinations_count(i,2)
    ans+=comb[i]

for i in range(n):
    pans=ans
    if cnt[a[i]] in comb:
        pans-=comb[cnt[a[i]]]
    c=cnt[a[i]]-1
    if c>1:
        if not c in comb:
            comb[c]=combinations_count(c,2)
        pans+=comb[c]
    print(pans)
### BUGGY CODE ###

N, K = map(int,input().split())
nums = list(map(int,input().split()))
ans = []

for i in range(N):
  ans.append((nums[i]+1)/2)

M = sum(ans[0:K])
for i in range(1,N-K+1):
  S = sum(ans[i:i+K])
  M = max(M,S)

print(M)

### FIXED CODE ###

N, K = map(int,input().split())
nums = list(map(int,input().split()))
ans = []

for i in range(N):
  ans.append((nums[i]+1)/2)

M = sum(ans[0:K])
S = M
for i in range(K,N):
  S = S + ans[i] - ans[i-K]
  M = max(M,S)

print(M)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

N=int(input())
n=[[]for i in range(N+1)]

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

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

L[K]=0

def dfs(x):
    for i in n[x]:
        if L[i[0]]==-1:
            L[i[0]]=L[x]+i[1]
            dfs(i[0])
dfs(K)
#print(n)
#print(L)

for i in range(Q):
    x,y=map(int,input().split())
    print(L[x]+L[y])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N=int(input())
n=[[]for i in range(N+1)]

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

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

L[K]=0

def dfs(x):
    for i in n[x]:
        if L[i[0]]==-1:
            L[i[0]]=L[x]+i[1]
            dfs(i[0])
dfs(K)
#print(n)
#print(L)

for i in range(Q):
    x,y=map(int,input().split())
    print(L[x]+L[y])
### BUGGY CODE ###

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

if m == 1:
  l, r = map(int, input().split())
  print(r-l+1)
else:
  l, r = map(int, input().split())
  ans = list(range(l, r+1))
  for _ in range(m-1):
    l, r = map(int, input().split())
    lr_list = list(range(l, r+1))
    ans = [a for a in ans if lr_list.count(a) == 1]
    if len(ans) == 0:
      break
  print(len(ans))

### FIXED CODE ###

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

if m == 1:
  l, r = map(int, input().split())
  print(r-l+1)
else:
  ls, rs = [], []
  for _ in range(m):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)
  ans = min(rs) - max(ls) + 1
  if ans > 0:
    print(ans)
  else:
    print(0)
### BUGGY CODE ###

a,b,x=map(int,input().split())
k=a
ans=0
while b>=k:
    if k%x==0:
        ans+=1
    k+=1
print(ans)

### FIXED CODE ###

a,b,x=map(int,input().split())
if a%x==0:
    print(b//x-a//x+1)
else:
    print(b//x-a//x)
### BUGGY CODE ###

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

weight = [None] * N
value = [None] * N
dp = [[None] * (W+1) for _ in range(N+1)]

for i in range(N):
  weight[i], value[i] = map(int, input().split())

for j in range(W+1):
  dp[0][j] = 0

for i in range(N):
  for w in range(W+1):
    if w >= weight[i]:
      dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w])
    else:
      dp[i+1][w] = dp[i][w]

ans = dp[N][W]
print(ans)

### FIXED CODE ###

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

weight = [None] * N
value = [None] * N
dp = [[None] * (W+1) for _ in range(N+1)]

for i in range(N):
  weight[i], value[i] = map(int, input().split())

for j in range(W+1):
  dp[0][j] = 0

for i in range(N):
  for w in range(W+1):
    if w >= weight[i]:
      dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w])
    else:
      dp[i+1][w] = dp[i][w]

ans = dp[N][W]
print(ans)
### BUGGY CODE ###

import sys
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    s = input()
    children = [0] * len(s)
    s += "E"
    start = 0
    now = 0
    while now < len(s)-1:
        r = 0
        l = 0
        while s[now] == "R":
            r += 1
            now += 1
        er = now - 1
        sl = now
        while s[now] == "L":
            l += 1
            now += 1
        count = now - start
        if count % 2 == 0:
            children[er] = count // 2
            children[sl] = count // 2
        else:
            if r % 2 == 1:
                children[er] = count // 2 + 1
                children[sl] = count // 2
            else:
                children[er] = count // 2
                children[sl] = count // 2 + 1
        start = now

    print(*children)

    return

main()


### FIXED CODE ###

import sys
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    s = input().rstrip()
    len_s = int(len(s))
    children = [0] * len_s
    s += "E"
    start = 0
    now = 0
    while now < len_s-1:
        r = 0
        l = 0
        while s[now] == "R":
            r += 1
            now += 1
        er = now - 1
        sl = now
        while s[now] == "L":
            l += 1
            now += 1
        count = now - start
        if count % 2 == 0:
            children[er] = count // 2
            children[sl] = count // 2
        else:
            if r % 2 == 1:
                children[er] = count // 2 + 1
                children[sl] = count // 2
            else:
                children[er] = count // 2
                children[sl] = count // 2 + 1
        start = now

    print(*children)

    return

main()
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
AB = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i] + B[j])
AB = sorted(AB, reverse=True)

if len(AB) > K:
    AB = AB[:K + 1]
ABC = []
for i in range(len(AB)):
    for j in range(Z):
        ABC.append(AB[i] + C[j])
ABC = sorted(ABC, reverse=True)
print(*ABC[:K])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)

ABC = []
for i in range(X):
    if (i + 1) > K:
        break
    for j in range(Y):
        if (i + 1) * (j + 1) > K:
            break
        for l in range(Z):
            if (i + 1) * (j + 1) * (l + 1) > K:
                break
            ABC.append(A[i] + B[j] + C[l])
ABC = sorted(ABC, reverse=True)
print(*ABC[:K])
### BUGGY CODE ###

# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
free = [1]*(N+1)
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)
    for j in range(l, r+1):
        free[j] = 0
# rより小さいインデックスで制約が満たすべき条件を伝播して高速化
for r in range(N-1, -1, -1):
    r_max[r] = min(r_max[r], r_max[r+1])
    g_max[r] = min(g_max[r], g_max[r+1])

def check(k, r, g, b):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    if free[k]:
        # N = 300, M = 0の場合等だと制約が少なすぎて定数が落ちない
        # => 制約が疎である場合は、制約がかかってない部分で切って高速化
        res = memo[key] = (3 * dfs(k+1, k, k, k+1)) % MOD
    else:
        # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
        res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

### FIXED CODE ###

MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)


X = {(0, 0): 3}
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    Z = [0]*(N+1)
    if C[b+1]:
        if t1 <= b < s0:
            for (r, g), v in X.items():
                if t2 <= g < s1:
                    # r <- b+1
                    Z[g] += v
                if t2 <= r < s1:
                    # g <- b+1
                    Z[r] += v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [0]*(N+1)
        for (r, g), v in X.items():
            # r <- b+1
            Z[g] += v
            # g <- b+1
            Z[r] += v;
    for z, v in enumerate(Z):
        if v:
            X[z, b] = v % MOD
print(sum(X.values()) % MOD)
### BUGGY CODE ###

from collections import deque
n,k=map(int,input().split())
S=input()+"*"
A=[0] if S[0]=="0" else []
num,cnt=S[0],0
for i in range(n+1):
    if num==S[i]:cnt +=1
    else:
        A.append(cnt)
        num=S[i]
        cnt=1

A=deque(A)
if len(A)<=1:print(sum(A));exit()
ans=0
while len(A)>1:
    ans=max(ans,sum([A[i] for i in range(min(2*k+1,len(A)))]))
    A.popleft()
    A.popleft()
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
S=input()+"*"

A=[0] if S[0]=="1" else []
cnt,fig=0,S[0]
for i in range(n+1):
    if fig!=S[i]:
        A.append(cnt)
        fig=S[i]
        cnt=1
    else:cnt +=1

if S[-2]=="0":A.append(0)
num=2*(k+1)
B=[[0,0]] if S[0]=="0" else []
for i in range(1,len(A)):
    A[i]=A[i]+A[i-1]
for i in range(0,len(A),2):
    B.append([A[i],A[i+1]])

C=[]
left=0
for i in range(max(0,len(B)-k)):
    C.append(B[k+i][1]-B[left+i][0])
print(max(C) if len(B)-k>0 else B[-1][1])
### BUGGY CODE ###

n,*s=[t.rstrip()for t in open(0)]
n=int(n)
c=0
for _ in range(n):
  c+=all(x==''.join(y)for x,y in zip(s,zip(*s)))*n
  s=s[1:]+s[:1]
print(c)

### FIXED CODE ###

n,*s=[t[:-1]for t in open(0)]
n=int(n)
c=0
for _ in range(n):
  c+=all(x==''.join(y)for x,y in zip(s,zip(*s)))*n
  s=s[1:]+s[:1]
print(c)