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

import sys
from collections import deque
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
S = [0 for _ in range(H)]
ans = [[0] * W for h in range(H)]

for h in range(H):
    S[h] = list(input().strip())

for i, s in enumerate(S):
    c = 0
    q = deque([])
    for k, j in enumerate(s):
        if j == '.':
            c += 1
            q.append(k)
            continue
        for qq in q:
            ans[i][qq] = c
        q = deque([])
        c = 0
    else:
        for qq in q:
            ans[i][qq] = c

ans_max = 0
for w in range(W):
    c = 0
    q = []
    for i, s in enumerate(S):
        if s[w] == '.':
            c += 1
            q.append(i)
            continue
        for qq in q:
            ans[qq][w] += c
            ans_max = max(ans_max, ans[qq][w])
        q = []
        c = 0
    else:
        for qq in q:
            ans[qq][w] += c
            ans_max = max(ans_max, ans[qq][w])
        q = []
        c = 0

print(ans_max-1)

### FIXED CODE ###

import sys
from collections import deque
import numpy as np
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
S = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)
u = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)
d = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)
l = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)
r = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)

for h in range(H):
    s = [1 if i == '.' else 0 for i in input().strip()]
    S[h + 1] = np.array([0] + s + [0])

for h in range(1, H + 1):
    u[h] = (u[h-1] + 1) * S[h]
    d[H+1-h] = (d[H+2-h] + 1) * S[H+1-h]

for w in range(1, W + 1):
    l[:, w] = (l[:, w-1] + 1) * S[:, w]
    r[:, W+1-w] = (r[:, W+2-w] + 1) * S[:, W+1-w]

ans = u+d+l+r
print(int(ans.max()-3))
### BUGGY CODE ###

N=list(map(int,input().split()))
n=N[0]
m=N[1]
A = []
for i in range(m):
  array = list(map(int,input().split()))
  array.sort()
  A.append(array)
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

X=get_unique_list(A)
#print(X)
R=[]

for j in range(1,n+1):
  c=1
  for h in range(len(X)):
    if j in X[h]:
      c+=1
  R.append(c)
    
  
print(max(R))

### FIXED CODE ###

class UnionFind(): # 0インデックス
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]


if __name__ == "__main__":
    N, M = map(int, input().split()) # N人、M個の関係
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    answer = 0
    for i in range(N):
        answer = max(answer, union_find.size(i))

    print(answer)
### BUGGY CODE ###

#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-ord('a'))
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
#print(seg[2])
for _ in range(q):
  d,a,b = input().split()
  if d == '1':
    b = ord(b) - ord('a')
    tmp = int(a) - 1
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp //= 2
    tmp = int(a) - 1
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp //= 2
  else:
    a = int(a) - 2
    b = int(b) - 1
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp % 2 == 1:
            l += seg[d][tmp-1]
          tmp //= 2
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp != 1:
        if tmp % 2 == 1:
          r += seg[d][tmp-1]
        tmp //= 2
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)

### FIXED CODE ###

#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp >>= 1
    tmp = int(a)
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp >>= 1
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp & 1:
            l += seg[d][tmp-1]
          tmp >>= 1
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp != 1:
        if tmp & 1:
          r += seg[d][tmp-1]
        tmp >>= 1
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)
### BUGGY CODE ###

from collections import defaultdict

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

lamp = {}
for i in range(1, N+1):
    lamp[i] = A[i-1]

for k in range(K):
    lamp_next = defaultdict(lambda: 0)
    for i in range(1, N+1):
        l = i - lamp[i]
        if l < 1:
            l = 1
        r = i + lamp[i]
        if r > N:
            r = N
        for j in range(l, r+1):
            lamp_next[j] += 1
    lamp = lamp_next
    if all(lamp[i]==N for i in range(1, N+1)):
        break

ans = [lamp[i] for i in range(1, N+1)]
print(*ans)

### FIXED CODE ###

import itertools

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

for _ in range(K):
    B = [0] * N
    for i in range(N):
        l = max(0, i-A[i])
        r = min(N-1, i+A[i])
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
    B = list(itertools.accumulate(B))
    A = B.copy()
    if A == [N] * N:
        break
print(*A)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    s = input()
    k = int(input())
    extracted = list()
    s_len = len(s)

    for i in range(1, s_len + 1):
        start = 0
        ended = i

        for j in range(s_len - i + 1):
            sub_str = s[start:ended]

            if sub_str not in extracted:
                extracted.append(sub_str)

            start += 1
            ended += 1

    sorted_extracted = sorted(extracted)
    print(sorted_extracted[k - 1])


### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    s = input()
    k = int(input())
    extracted = list()
    s_len = len(s)

    for i in range(1, min(k, s_len) + 1):
        start = 0
        ended = i

        for j in range(s_len - i + 1):
            sub_str = s[start:ended]

            if sub_str not in extracted:
                extracted.append(sub_str)

            start += 1
            ended += 1

    sorted_extracted = sorted(extracted)
    print(sorted_extracted[k - 1])
### BUGGY CODE ###

from copy import copy
n = int(input())
a = [int(x) for x in input().split()]
ans1=[(-1)**i for i in range(n)]

b=copy(a)
res_b=0
c=copy(a)
res_c=0
for i in range(n):
  if ans1[i]*sum(b[:i+1])>0:
    pass
  else:
    b[i]=ans1[i]-sum(b[:i])
    res_b+=abs(b[i]-a[i])
  if -1*ans1[i]*sum(c[:i+1])>0:
    pass
  else:
    c[i]=-1*ans1[i]-sum(c[:i])
    res_c+=abs(c[i]-a[i])
  
print(min(res_b,res_c))

### FIXED CODE ###

from copy import copy
n = int(input())
a = [int(x) for x in input().split()]
ans1=[(-1)**i for i in range(n)]

b=copy(a)
res_b=0
sb=0
c=copy(a)
res_c=0
sc=0
for i in range(n):
  sb+=a[i]
  if ans1[i]*sb>0:
    pass
  else:
    b[i]=ans1[i]-(sb-b[i])
    sb=sb-a[i]+b[i]
    res_b+=abs(b[i]-a[i])

  sc+=a[i]
  if -1*ans1[i]*sc>0:
    pass
  else:
    c[i]=-1*ans1[i]-(sc-c[i])
    sc=sc-a[i]+c[i]
    res_c+=abs(c[i]-a[i])
  
print(min(res_b,res_c))
### BUGGY CODE ###

S=input()
Q=int(input())
import sys
from collections import deque
d=deque()
for _ in S:
  d.append(_)
 
for _ in range(Q):
  s = list(sys.stdin.readline())
  if s[0]=="1":
    lis=list(d)
    lis=lis[::-1]
    d=deque(lis)
  else:
    if s[2]=="1":
      d.appendleft(s[4])
    else:
      d.append(s[4])
      
print("".join(d))

### FIXED CODE ###

S=input()
Q=int(input())
import sys
from collections import deque
d=deque()
for _ in S:
  d.append(_)
flag=False

for _ in range(Q):
  s = list(sys.stdin.readline())
  if s[0]=="1":
    if flag:
      flag=False
    else:
      flag=True
  else:
    if s[2]=="1":
      if flag:
        d.append(s[4])
      else:
        d.appendleft(s[4])
    else:
      if flag:
        d.appendleft(s[4])
      else:
        d.append(s[4])
      
if flag:
  d.reverse()
  
print("".join(d))
### BUGGY CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md=10**9+7
    n, m = MI()
    rtol = defaultdict(list)
    for _ in range(m):
        l, r, x = MI()
        rtol[r].append([l, x])
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    dp[0][0][0] = 1
    ans = 0
    for r in range(n):
        for g in range(n):
            for b in range(n):
                pre = dp[r][g][b]
                if pre == 0: continue
                i = max(r, g, b) + 1
                flag=False
                for l, x in rtol[i-1]:
                    over_l = [r >= l, g >= l, b >= l]
                    if sum(over_l)!=x:
                        flag=True
                        break
                if flag:continue
                dp[i][g][b] = (pre+dp[i][g][b])%md
                dp[r][i][b] = (pre+dp[r][i][b])%md
                dp[r][g][i] = (pre+dp[r][g][i])%md
    for l, x in rtol[n]:
        for i in range(n):
            for j in range(n):
                over_l = [i >= l, j >= l]
                if sum(over_l)+1 != x:
                    dp[i][j][n]=0
                    dp[i][n][j]=0
                    dp[n][j][i]=0

    ans+=sum(dp[i][j][n] for i in range(n) for j in range(n))
    ans%=md
    ans+=sum(dp[i][n][j] for i in range(n) for j in range(n))
    ans%=md
    ans+=sum(dp[n][j][i] for i in range(n) for j in range(n))
    ans%=md
    print(ans)

main()


### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

# 一番後ろの色を(赤に)固定した上で、もらうDPに書き換え
def main():
    md = 10 ** 9 + 7
    n, m = MI()
    rtol = defaultdict(list)
    for _ in range(m):
        l, r, x = MI()
        rtol[r].append([l, x])
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for k in range(1, n + 1):
        for i in range(k - 1):
            dp[i][k - 1] = dp[k - 1][i] = sum(dp[i][:k - 1]) % md
        for l, x in rtol[k]:
            if x == 1:
                for i in range(l, k):
                    for j in range(k):
                        dp[i][j] = dp[j][i] = 0
            if x == 2:
                for i in range(l, k):
                    for j in range(i + 1, k):
                        dp[i][j] = dp[j][i] = 0
                for i in range(l):
                    for j in range(i + 1):
                        dp[i][j] = dp[j][i] = 0
            if x == 3:
                for i in range(l):
                    for j in range(k):
                        dp[i][j] = dp[j][i] = 0

    # p2D(dp)
    print(sum(sum(dr) for dr in dp) * 3 % md)

main()
### BUGGY CODE ###

import numpy as np
N = int(input())
P = np.array(list(map(int, input().split())))

ans = 0
for i in range(N):
    for j in range(i):
        if P[j] < P[i]:
            break
    else:
        ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0
v = P[0]
for i in P:
    if i <= v:
        ans += 1
        v = i
print(ans)
### BUGGY CODE ###

from collections import Counter

n = int(input())
nums = [int(s) for s in input().split()]
counter = Counter(nums)

for outlier in nums:
    res = 0
    counter[outlier] -= 1

    for cnt in counter.values():
        res += (cnt - 1)*cnt // 2

    counter[outlier] += 1
    print(res)




### FIXED CODE ###

from collections import Counter

n = int(input())
nums = [int(s) for s in input().split()]
counter = Counter(nums)
res = 0

for cnt in counter.values():
    res += (cnt - 1)*cnt // 2

for outlier in nums:
    cnt = counter[outlier]
    if cnt <= 1:
        print(res)
    else:
        print(res - cnt + 1)
### BUGGY CODE ###

#初見じゃ無理だった。DPを使う
#標準入力
import math
import numpy as np
H, N = map(int, input().split())
AB = []
max_A = 0
for i in range(N):
    ab = list(map(int, input().split()))
    if max_A < ab[0] :
        max_A = ab[0]
    AB.append(ab)
AB = np.array(AB)

 #DP
DP = [0] * (H + max_A)
for i in range(1, H + max_A ): #DP[i] の最小値を求めていく
    tmp_mini = 10 ** 8
    for j in range(N):
        if i - AB[j][0] >= 0:
            tmp = DP[i - AB[j][0]] + AB[j][1]
            if tmp_mini > tmp:
                tmp_mini = tmp
    DP[i] = tmp_mini
print(min(DP[H: H + max_A]))


### FIXED CODE ###

#初見じゃ無理だった。DPを使う
#標準入力
import math
H, N = map(int, input().split())
AB = []
max_A = 0
for i in range(N):
    ab = list(map(int, input().split()))
    if max_A < ab[0] :
        max_A = ab[0]
    AB.append(ab)

 #DP
DP = [0] * (H + max_A)
for i in range(1, H + max_A ): #DP[i] の最小値を求めていく
    tmp_mini = 10 ** 8
    for j in range(N):
        if i - AB[j][0] >= 0:
            tmp = DP[i - AB[j][0]] + AB[j][1]
            if tmp_mini > tmp:
                tmp_mini = tmp
    DP[i] = tmp_mini
print(min(DP[H: H + max_A]))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def _solve(N: int, K: int, A: "List[int]"):
    ret = sum(A)
    digits = 0
    while K >= 2 ** digits:
        digits += 1
    counts = [0] * digits
    for num in A:
        n = num
        idx = 0
        while n > 0 and idx < digits:
            if n % 2 == 1:
                counts[idx] += 1
            idx += 1
            n //= 2
    tmp = 0
    for idx, c in enumerate(counts):
        if N - 2 * c > 0 and tmp + 2 ** idx <= K:
            ret += (2 ** idx) * (N - 2 * c)
            tmp += 2 ** idx

    if digits > 0:
        last = counts[-1]
        if N - 2 * last > 0:
            most_bit = 2 ** (digits - 1)
            K_ = K - most_bit
            ret = max(ret, _solve(N, K_, A) + most_bit * (N - 2 * last))
    #print(N, K, A)
    #print(ret)
    #print('--------------- ')
    return ret

def solve(N: int, K: int, A: "List[int]"):
    ret = _solve(N, K, A)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def _solve(counts, k, n, used=[]):
    ret = 0
    digits = 0
    while k >= 2 ** digits:
        digits += 1
    tmp = 0
    for idx, c in enumerate(counts):
        if not idx in used:
            if n - 2 * c > 0 and tmp + 2 ** idx <= k:
                ret += (2 ** idx) * (n - c)
                tmp += 2 ** idx
            else:
                ret += (2 ** idx) * c
    #print('k : %d, digits : %d, ret : %d, used : %s' % (k, digits, ret, used))
    #print('counts : %s' % (counts))
    if digits > 0:
        last = counts[digits - 1]
        if n - 2 * last >= 0:
            most_bit = 2 ** (digits - 1)
            k_ = k - most_bit
            #ret = max(ret, _solve(counts[:digits - 1], k_, n) + most_bit * (n - last))
            ret = max(ret, _solve(counts, k_, n, used + [digits - 1]) + most_bit * (n - last))
        #most_bit = 2 ** (digits - 1)
        #k_ = k - most_bit
        #ret = max(ret, _solve(counts, k_, n, used + [digits - 1]) + most_bit * (n - last))
    #print(ret)
    return ret


def solve(N: int, K: int, A: "List[int]"):
    counts = [0] * 45
    for num in A:
        n = num
        idx = 0
        while n > 0:
            if n % 2 == 1:
                counts[idx] += 1
            idx += 1
            n //= 2
    ret = _solve(counts, K, N)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, A)

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

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import numpy as np

def main():
  N, Q = map(int, input().strip().split(' '))
  S = input()
  ans = []
  ls = np.array([i for i in range(len(S)-1) if S[i:i+2] == 'AC'])
  for _ in range(Q):
    l, r = map(int, input().strip().split(' '))
    l -= 1
    _ls = ls[l<=ls]
    _ls = _ls[_ls<(r-1)]
    ans += [len(_ls)]
  [print(a) for a in ans]
  pass

if __name__=='__main__':
  main()

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import numpy as np

def main():
  N, Q = map(int, input().strip().split(' '))
  S = input()
  ans = []
  rs = np.zeros(len(S), dtype=np.int)
  for i in range(1,len(S)):
    if S[i-1:i+1] == 'AC':
      rs[i] = rs[i-1]+1
    else:
      rs[i] = rs[i-1]
  for _ in range(Q):
    l, r = map(int, input().strip().split(' '))
    l -= 1
    r -= 1
    ans += [rs[r]-rs[l]]
  [print(a) for a in ans]
  pass

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

N = int(input())
S = [list(input()) for _ in range(N)]

def generate(A, B):
    T = [[""] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            ni = (i + A) % N
            nj = (j + B) % N
            T[ni][nj] = S[i][j]
    flag = True
    for i in range(N):
        for j in range(N):
            flag &= T[i][j] == T[j][i]
    return flag

ans = 0

for A in range(N):
    ans += N * generate(A, 0)

print(ans)

### FIXED CODE ###

N = int(input())
S = [list(input()) for _ in range(N)]

def generate(A, B):
    T = [[""] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            ni = (i + A) % N
            nj = (j + B) % N
            T[ni][nj] = S[i][j]
    flag = True
    for i in range(N):
        for j in range(N):
            flag &= T[i][j] == T[j][i]
    return flag

ans = 0

for A in range(N):
    ans += N * generate(A, 0)

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

N,K,Q=[int(i) for i in input().split()]
A = list(map(int,[input() for i in range(Q)]))

points = [K] * N

for a in A :
    for j,p in enumerate(points) :
        if j+1 != a :
            points[j] -= 1

for p in points :
    print('No') if p <= 0 else print('Yes')
        
    

### FIXED CODE ###

N,K,Q=[int(i) for i in input().split()]
A = list(map(int,[input() for i in range(Q)]))
 
points = [K] * N
answers = [0] * N

for a in A :
   answers[a-1] += 1

sum = [x + y for (x, y) in zip(points, answers)]
aaa = [x - Q for (x) in sum]
for p in aaa :
    print('No') if p <= 0 else print('Yes')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import re
# 入力された文字列
string = input()

# 最大処理数。100000以下なら文字列長。
max = min(len(string), 100000)

raw_length = len(string)

# 削除があった場合True
del_flg = True

# 削除文字がなくなるまでループする
while del_flg:
    del_flg = False
    before_length = len(string)
    #string = string.replace('01', '').replace('10', '')
    regex = '01|10'
    string = re.sub(regex, '', string)
    after_length = len(string)
    
    if before_length != after_length:
        del_flg = True

print((raw_length - len(string)))

### FIXED CODE ###

# -*- coding: utf-8 -*-

string = input()

red_count  = string.count('0')
blue_count = string.count('1')

print(min(red_count, blue_count) * 2)
### BUGGY CODE ###

from sys import stdin
def main():
    number = int(input())
    num_list = list(map(int, stdin.readline().split()))
    sum = 0
    for i in range(number):
        temp = num_list[i]
        for j in range(i+1, number):
            sum += temp*num_list[j]
    div = sum // (10**9 + 7)
    print(sum - div * (10**9 + 7))
if __name__ == '__main__':
    main()

### FIXED CODE ###

from sys import stdin
import itertools
def main():
    number = int(input())
    num_list = list(map(int, stdin.readline().split()))
    num_list_sum = sum(num_list)
    total = 0
    for i in range(number):
        num_list_sum -= num_list[i]
        total += num_list[i] * num_list_sum
    print(total % (10**9+7))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    def cnt(s):
        if len(s) == 1:
            if s[0] == "1":
                return 3
            else:
                return 1
        if s[0] == "0":
            return cnt(s[1:]) % MOD
        else:
            return (cnt(s[1:]) % MOD) * 2 + 3 ** (len(s) - 1) % MOD

    answer = cnt(L) % MOD

    print(answer)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import queue


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD
    N = len(L)
    if L[-1] == "0":
        answer = 1
    else:
        answer = 3
    for i in range(1, N):
        if L[N - i - 1] == "1":
            answer = answer * 2 + pow[i]
            answer %= MOD
        else:
            continue
    print(answer)


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

n = int(input())
i = 1
ret = ""
while True:
    x = i
    if  x % 3 == 0:
        ret += " " + str(i)
        i+=1
        if i > n:
            print(ret)
            break


### FIXED CODE ###

#
# 5d
#

def main():
    n = int(input())
    s = ""
    for i in range(1, n+1):
        x = i
        if x % 3 == 0 or x % 10 == 3:
            s += " " + str(i)
        else:
            x //= 10
            while x:
                if x % 10 == 3:
                    s += " " + str(i)
                    break
                x //= 10
    print(s)


if __name__ == '__main__':
    main()