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

N = int(input())
l = [input() for i in range(N)]
for i in range(N):
    l[i] = ''.join(sorted(l[i]))
count = 0
for i in range(N-1):
    for j in range(i+1,N):
        if(l[i]==l[j]):
            count += 1
print(count)

### FIXED CODE ###

N = int(input())
l = [input() for i in range(N)]
mydict = {}
times = [1]*N
count = 0
value = 1

for i in range(N):
    l[i] = ''.join(sorted(l[i]))
    if l[i] in mydict.keys():
        count += times[mydict[l[i]]]
        times[mydict[l[i]]] += 1
    else:
        mydict[l[i]] = value
        value += 1
print(count)
### BUGGY CODE ###

n = int(input())
left = 0
right = n - 1
print(left, flush=True)
sl = input()
if sl[0] == "V":
    quit()
while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    sm = input()
    if sm[0] == "V":
        quit()

    if mid % 2:
        if sl != sl:
            left = mid
        else:
            right = mid
    else:
        if sl != sl:
            right = mid
        else:
            left = mid


### FIXED CODE ###

n = int(input())

left = 0
right = n
print(left, flush=True)
sl = input()
if sl[0] == "V":
    quit()
while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    sm = input()
    if sm[0] == "V":
        quit()

    if ((mid - left) % 2 == 1) ^ (sl == sm):
        left = mid
        sl = sm
    else:
        right = mid
### BUGGY CODE ###

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

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

SD=[0]*N

for x,d in G[K-1]:
    SD[x]=d

for i in range(N):
    if i==K-1:continue
    ans=[]
    seen=[0]*N
    stack=[[i,0]]
    seen[i]=1
    while stack:
        x,d=stack.pop()
        if x==K-1:
            ans.append(d)
        elif SD[x]!=0:
            ans.append(d+SD[x])
        else:
            for y,co in G[x]:
                if seen[y]==0:
                    stack.append([y,d+co])
                    seen[y]=1
    SD[i]=min(ans)


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



### FIXED CODE ###

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

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

SD=[0]*N
seen=[0]*N
stack=[]
stack.append([K-1,0])
seen[K-1]=1
while stack:
    x,d=stack.pop()
    for y,d0 in G[x]:
        if seen[y]==0:
            SD[y]=d+d0
            stack.append([y,d+d0])
            seen[y]=1
for i in range(Q):
    x,y=map(int,input().split())
    ans=SD[x-1]+SD[y-1]
    print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
ans = s.count("R") * s.count("G") * s.count("B")
for i in range(n):
    for j in range(n):
        if i+2*j < n:
            if (s[i],s[i+j],s[i+2*j]) == ("R","G","B") or (s[i],s[i+j],s[i+2*j]) == ("R","B","G")or (s[i],s[i+j],s[i+2*j]) == ("G","B","R") or (s[i],s[i+j],s[i+2*j]) == ("G","R","B") or (s[i],s[i+j],s[i+2*j]) == ("B","G","R") or (s[i],s[i+j],s[i+2*j]) == ("B","R","G"):
                ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count("R") * s.count("G") * s.count("B")
for i in range(n):
    for j in range(n):
        if i+2*j < n:
            if (s[i],s[i+j],s[i+2*j]) == ("R","G","B") or (s[i],s[i+j],s[i+2*j]) == ("R","B","G")or (s[i],s[i+j],s[i+2*j]) == ("G","B","R") or (s[i],s[i+j],s[i+2*j]) == ("G","R","B") or (s[i],s[i+j],s[i+2*j]) == ("B","G","R") or (s[i],s[i+j],s[i+2*j]) == ("B","R","G"):
                ans -= 1
print(ans)
### BUGGY CODE ###

import collections

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

visited = [[-float("inf")]*(w) for _ in range(h)]
q = collections.deque([])

a = []
for i in range(h):
    _a = list(input())
    a.append(_a)
    for j in range(w):
        if _a[j] == "#":
            q.appendleft([i, j])
            visited[i][j] = 0

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

while 0 < len(q):
    cy, cx = q.pop()
    for _dx, _dy in zip(dx, dy):
        x = cx + _dx
        y = cy + _dy

        if x < 0 or w <= x or y < 0 or h <= y:
            continue

        if a[y][x] == "." and visited[y][x] == -float("inf"):
            visited[y][x] = visited[cy][cx] + 1
            q.appendleft([y, x])

ans = -1
for v in visited:
    ans = max(ans, max(v))
print(ans)


### FIXED CODE ###

from subprocess import call
call (('pypy3', '-c', """
from collections import deque

def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()

"""))
### BUGGY CODE ###

n, m  = map(int, input().split())
nums  = list(map(int, input().split()))
length = len(nums)

for i in range(m):
    b, c = map(int, input().split())
    nums.extend([c] * b)
    
nums = sorted(nums, reverse=True)
print(sum(nums[:length]))

### FIXED CODE ###

import numpy as np

n, m  = map(int, input().split())
nums  = list(map(int, input().split()))
length = len(nums)

arr = np.array([list(map(int, input().split())) for i in range(m)])
mask = arr.T[1].argsort()[::-1]
arr = arr[mask]

cnt = 0
for b, c in arr:
    nums.extend([int(c)]*b)
    cnt += b
    if cnt > length:
        break

nums = list(nums)
nums.sort(reverse=True)

print(sum(nums[:length]))
### BUGGY CODE ###

x = int(input())
for n in 10 ** 10 ** 10:
  if x <= (101 ** n) / (100 ** (n - 1)):
    print(n)

### FIXED CODE ###

x = int(input())
n = 0
mon = 100
while mon < x:
  mon *= 1.01
  mon = int(mon)
  n += 1
  
print(n)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
fr = {i:[] for i in range(N)}
for _ in range(M):
    a, b = list(map(int, input().split()))
    if b-1 not in fr[a-1]:
        fr[a-1].append(b-1)
    if a-1 not in fr[b-1]:
        fr[b-1].append(a-1)

remain = [i for i in range(N)]
groups = []
while remain!=[]:
    g = []
    o = remain.pop(0)
    g.append(o)
    cands = fr[o]
    while cands!=[]:
        n = cands.pop(0)
        g.append(n)
        remain.remove(n)
        cands.extend([num for num in fr[n] if num not in g and num not in cands])
    groups.append(g)

ans = 0
for one in groups:
    if len(one)>ans:
        ans = len(one)
print(ans)

### FIXED CODE ###

class UnionFind():
    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)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = list(map(int, input().split()))
u = UnionFind(N)
for _ in range(M):
    a, b = list(map(int, input().split()))
    u.union(a-1,b-1)
ans = []
for i in range(N):
    ans.append(u.find(i))
from collections import Counter
c=Counter(ans)
print(max(c.values()))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")

import math
import collections


def trial_division_sqrt(n):
    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def solve(N: int, a: "List[int]"):
    print(sum([trial_division_sqrt(v)[2] for v in a]))
    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
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")

import math
import collections


def solve(N: int, a: "List[int]"):
    print(int(sum([math.log2(v & -v) for v in a])))
    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
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


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


# -*- coding: utf-8 -*-
import random
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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

def warshall_floyd(g):
    d = g
    N = len(g)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


def slv():
    N, M, L = read_int_n()
    g = [[sys.maxsize]*(N) for _ in range(N)]
    for i in range(N):
        g[i][i] = 0
    for _ in range(M):
        a, b, c = read_int_n()
        if c > L:
            continue
        g[a-1][b-1] = c
        g[b-1][a-1] = c
    
    d = g
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    gg = [[sys.maxsize]*(N) for _ in range(N)]
    for u in range(N):
        for v in range(N):
            if d[u][v] <= L:
                gg[u][v] = 1
    
    d = gg
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    Q = read_int()
    for _ in range(Q):
        s, t = read_int_n()
        c = d[s-1][t-1]
        if c != sys.maxsize:
            print(c-1)
        else:
            print(-1)



def main():
    slv()
    # N, M, L = read_int_n()
    # ABC = [read_int_n() for _ in range(M)]
    # Q = read_int()
    # ST = [read_int_n() for _ in range(Q)]
    
    # (slv(N, M, L, ABC, Q, ST))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    n, m, l = list(map(int, input().rstrip('\n').split()))
    INF = 10 ** 11
    w = [[INF] * n for _ in range(n)]
    wl = [[INF] * n for _ in range(n)]

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

    for i in range(m):
        a, b, c = list(map(int, input().rstrip('\n').split()))
        if c <= l:
            w[a - 1][b - 1] = c
            w[b - 1][a - 1] = c

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

    for i in range(n):
        for j in range(n):
            if w[i][j] <= l:
                wl[i][j] = 1
    for i in range(n):
        for j in range(n):
            for k in range(n):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    q = int(input().rstrip('\n'))
    for i in range(q):
        s, t = list(map(int, input().rstrip('\n').split()))
        if wl[s-1][t-1] == INF:
            print(-1)
        else:
            print(wl[s-1][t-1] - 1)


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

import sys
import operator

n, m = map(int, input().split())
a = [int(x) for x in sys.stdin.readline().rstrip().split()]
a.sort()
cards = [[int(x) for x in sys.stdin.readline().rstrip().split()] for _ in range(m)]
cards.sort(key=operator.itemgetter(1), reverse=True)
for b, c in cards:
    if c <= a[0]:
        break
    for idx in range(b):
        if c <= a[idx]:
            break
        a[idx] = c
    a.sort()
print(sum(a))


### FIXED CODE ###

import sys
import operator

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

a = [int(x) for x in sys.stdin.readline().rstrip().split()]
a.sort()

cards = [[int(x) for x in sys.stdin.readline().rstrip().split()] for _ in range(m)]
cards.sort(key=operator.itemgetter(1), reverse=True)

a_idx = 0
a_len = len(a)

for i in range(len(cards)):
    for j in range(cards[i][0]):
        if a_idx == a_len or a[a_idx] >= cards[i][1]:
            break
        else:
            a[a_idx] = cards[i][1]
            a_idx += 1

print(sum(a))
### BUGGY CODE ###

n, m = [int(i) for i in input().split()]
islands = list(range(0, -(n+1), -1))
island_group = 1
bridges = []
for _ in range(m):
    bridges.append([int(i) for i in input().split()])

connection = []
for i, j in bridges[::-1]:
    if islands[i] == islands[j]:
        connection.append(0)
    else:
        connection.append(islands.count(islands[i]) * islands.count(islands[j]))
        group1, group2 = islands[i], islands[j]
        for k, v in enumerate(islands[:]):
            if v == group1 or v == group2:
                islands[k] = island_group
        island_group += 1

sum_ = 0
for i in connection[::-1]:
    sum_ += i
    print(sum_)


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self._par = [i for i in range(n + 1)]
        self._size = [1] * (n + 1)

    def find(self, x):
        if self._par[x] == x:
            return x
        else:
            self._par[x] = self.find(self._par[x])
            return self._par[x]

    def is_same_root(self, x, y):
        x = self.find(x)
        y = self.find(y)
        return x == y

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self._size[x] < self._size[y]:
            self._par[x] = y
            self._size[y] += self._size[x]
        else:
            self._par[y] = x
            self._size[x] += self._size[y]

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


def main():
    n, m = [int(i) for i in input().split()]
    bridges = [[int(i) for i in input().split()] for _ in range(m)]

    union_find = UnionFind(n)
    connection = []
    for i, j in bridges[::-1]:
        if union_find.is_same_root(i, j):
            connection.append(0)
        else:
            connection.append(union_find.size(i) * union_find.size(j))
            union_find.unite(i, j)

    sum_ = 0
    for i in connection[::-1]:
        sum_ += i
        print(sum_)


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

n,k=map(int,input().split())
c=list(map(int,input().split()))
s=list(set(c))
p=[]
if len(s)<=k:
    print(0)
else:
    for i in range(len(s)):
        p.append(c.count(s[i]))
    p.sort()
    print(sum(p[:len(s)-k]))

### FIXED CODE ###

import collections 
n,k=map(int,input().split())
c=list(map(int,input().split()))
l=collections.Counter(c)
s=l.most_common()
p=[]
if len(s)<=k:
    print(0)
else:
    d=0
    for a,b in s[:k]:
        d+=b
    print(n-d)
### BUGGY CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
for i in range(n):
    a = a[1:]
    ans += a[-2]
    a = a[:-2]
print(ans)


### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
for i in range(n):
    ans += a[3*n-2-2*i]
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
	dp[i]=min(dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i))
print(dp[-1])

### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * n
dp[0] = 0
for i in range(1,n):
    H = h[i]
    dp[i] = min([dp[j] + abs(h[j] - H) for j in range(max(0, i - k), i)])
print(dp[-1])
### BUGGY CODE ###

import collections
import math
def cmb(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
la = list(map(int,input().split()))
all = 0
for i in range(N+1):
    all += cmb(la.count(i),2)
for k in range(N):
    print(all-la.count(la[k])+1)


### FIXED CODE ###

import collections
import math
def cmb(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
la = list(map(int,input().split()))
all = 0
c = collections.Counter(la)
#print(c)
for i in range(N+1):
    all += cmb(c[i],2)
#print(all)
for k in range(N):
    print(all-c[la[k]]+1)
### BUGGY CODE ###

def calc_allocatable_packet(packets, num_of_trucks, p_max):
    num_of_packets = len(packets)
    next_p = 0  # ?????°?????????????????° ??? ?¬????packet[i]?????????????????????
    for t in range(num_of_trucks):
        payload = 0  # ??????????????????????????????
        while next_p < num_of_packets:
            if payload + packets[next_p] <= p_max:  # ?¬?????????????????????§???????
                payload += packets[next_p]
                next_p += 1
            else:
                break  # ?¬???????????????????
    return next_p


def calc_minimum_payload(packets, num_of_trucks):
    num_of_packets = len(packets)
    p_max = packets[0]
    result = calc_allocatable_packet(packets, num_of_trucks, p_max)
    while result < num_of_packets:
        p_max += 1
        result = calc_allocatable_packet(packets, num_of_trucks, p_max)
    return p_max



if __name__ == '__main__':
    # ??????????????\???
    num_of_packets, num_of_trucks = [int(x) for x in input().split(' ')]
    packets = [int(input()) for _ in range(num_of_packets)]
    # packets = [8, 1, 7, 3, 9]

    # ???????????????
    result = calc_minimum_payload(packets, num_of_trucks)

    # ???????????¨???
    print(result)

### FIXED CODE ###

def calc_allocatable_packet(packets, num_of_trucks, p_max):
    """ ?????????????????°?????????????????§?????????????±?????????????n??°??????????????????????????????????????°????±??????? """
    num_of_packets = len(packets)
    next_p = 0  # ?????°?????????????????° ??? ?¬????packet[i]?????????????????????
    for t in range(num_of_trucks):
        payload = 0  # ??????????????????????????????
        while next_p < num_of_packets:
            if payload + packets[next_p] <= p_max:  # ?¬?????????????????????§???????
                payload += packets[next_p]
                next_p += 1
            else:
                break  # ?¬???????????????????
    return next_p


def calc_minimum_payload(packets, num_of_trucks):
    num_of_packets = len(packets)
    lower_limit = packets[0]
    upper_limit = 10000 * num_of_packets

    while lower_limit < upper_limit:
        middle = (lower_limit + upper_limit) // 2
        result = calc_allocatable_packet(packets, num_of_trucks, middle)
        if result < num_of_packets:
            lower_limit = middle + 1
        else:
            upper_limit = middle

    return lower_limit


if __name__ == '__main__':
    # ??????????????\???
    num_of_packets, num_of_trucks = [int(x) for x in input().split(' ')]
    packets = [int(input()) for _ in range(num_of_packets)]
    # num_of_packets, num_of_trucks = 0, 0
    # packets = []
    # with open('ALDS1_4_D_in25.txt') as f:
    #    for line in f:
    #       if ' ' not in line:
    #           packets.append(int(line))
    #       else:
    #           num_of_packets, num_of_trucks = [int(x) for x in line.split(' ')]



    # ???????????????
    result = calc_minimum_payload(packets, num_of_trucks)

    # ???????????¨???
    print(result)
### BUGGY CODE ###

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from random import randint

    def score(t):
        memo = [0] * 26
        ans = 0
        for i, tt in enumerate(t):
            ans += s[i][tt - 1]
            memo[tt - 1] = i + 1
            for m, cc in zip(memo, c):
                ans -= cc * (i + 1 - m)
        return ans

    d = int(readline())
    c = list(map(int, readline().split()))
    s = [list(map(int, readline().split())) for _ in range(d)]
    t = [0] * d
    r = [0] * d
    check = 0
    for i in range(d):
        t[i] = s[i].index(max(s[i])) + 1
        check = score(t)
    for i in range(10 ** 4):
        for j in range(d):
            r[j] = randint(1, 26)
        if check < score(r):
            t = r
    print('\n'.join(map(str, t)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    d = int(readline())
    c = list(map(int, readline().split()))
    s = [list(map(int, readline().split())) for _ in range(d)]
    for i in range(d):
        print(s[i].index(max(s[i])) + 1)


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

n,a,b=map(int,input().split())
x=n%(a+b)
if x in list(i for i in range(1,a+1)):
    print(a*(n//(a+b))+x)
elif x==0:
    print(a*(n//(a+b)))
else:
    print(a*((n//(a+b))+1))

### FIXED CODE ###

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

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

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

def lcm(a,b):
  return int(a*b/gcd(a,b))

X = ["" for i in range(lcm(N,M))]
L = len(X)
flag = True

for i in range(N):
  X[(i+1-1)*int(L/N)] = S[i]

for i in range(M):
  X[(i+1-1)*int(L/M)] = T[i]

for i in range(N):
  if X[(i+1-1)*int(L/N)] == S[i]:
    continue
  else:
    flag = False
    break
if flag:
  for i in range(M):
    if X[(i+1-1)*int(L/M)] == T[i]:
      continue
    else:
      flag == False
      break

if flag:  
  print(L)
else:
  print(-1)

### FIXED CODE ###

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

def lcm(a,b):
  return int(a*b/gcd(a,b))
 
N,M = map(int,input().split())
S = input()
T = input()
L = lcm(N,M)
flag = True
min_len = min(N,M)
s_index = int(int(L/M)/gcd(int(L/M),int(L/N)))
t_index = int(int(L/N)/gcd(int(L/M),int(L/N)))

if N == M:
  for i in range(N):
    if S[i] == T[i]:
      continue
    else:
      flag = False
      break
else:
  for i in range(min_len):
    if i * s_index < N-1 and i*t_index < M - 1:
      if S[i*s_index] == T[i*t_index]:
        continue
      else:
        flag = False
        break
    else:
      break
    
if flag:  
  print(L)
else:
  print(-1)
### BUGGY CODE ###

m=lambda x:max(map(max,[[sum(x[j:j+i+1]) for j in range(len(x)-i)] for i in range(len(x))]))
while True:
    n=int(input())
    if n==0:break
    print(m([int(input()) for i in range(n)]))


### FIXED CODE ###

while True:
    n=int(input())
    if n==0:break
    l=[int(input()) for i in range(n)]
    s=0
    m=0
    for li in l:
        s=max(0,s+li)
        m=max(m,s)
    print(m if m else max(l))