목걸이

바이트랜드(Byteland)는 보석 세공사 바이트맨(Byteman)이 만드는 아름다운 목걸이로 유명하다. 목걸이는 보석을 실에 꿰어 만든 고리이다. 보석은 26가지 종류가 있으며 각각 소문자 알파벳 a부터 z로 나타낸다(같은 종류의 보석끼리는 구별할 수 없다). 바이트맨은 완전히 똑같은 목걸이를 두 번 만들지 않기 때문에, 지금까지 만든 모든 목걸이의 설명을 기록해 둔다.

어떤 목걸이는 매우 길어서 설명을 압축된 형태로 저장한다. 하나의 설명은 여러 조각(fragment)의 나열이다. 각 조각은 패턴(문자열 하나)과 그 패턴이 몇 번 반복되는지를 나타내는 정수로 이루어지며, 조각들을 순서대로 이어 붙이면 목걸이가 된다. 예를 들어 패턴 abc를 2번, xyz를 1번, axc를 3번 반복하는 설명은 목걸이 abcabcxyzaxcaxcaxc를 나타낸다.

문제가 까다로운 이유는 목걸이가 고리이기 때문이다. 시작하는 보석이 정해져 있지 않아 어느 위치에서 읽기 시작해도 되고(목걸이를 돌릴 수 있고), 따라서 하나의 목걸이가 여러 설명으로 표현될 수 있다. 두 설명이 나타내는 고리를 회전시켜 서로 같게 만들 수 있으면 두 설명은 같은 목걸이를 나타낸다. 예컨대 위 목걸이는 cabcxyzaxcaxcaxcab 또는 xcaxcaxcabcabcxyza로도 쓸 수 있다.

두 설명이 주어질 때, 두 설명이 같은 목걸이를 나타내는지 판별하라.

입력은 두 줄이며 각 줄에 목걸이 설명이 하나씩 주어진다. 설명은 공백 하나로 구분된 토큰들의 나열이다. 먼저 패턴의 개수를 나타내는 정수 $n$이 주어지고 ($1 \le n \le 1000$), 이어서 $n$개의 패턴 블록이 온다. $i$번째 블록은 세 개의 토큰으로 이루어진다: 패턴의 길이를 나타내는 정수 $l_i$ ($1 \le l_i \le 10000$), 정확히 $l_i$개의 소문자로 이루어진 패턴 문자열 $s_i$, 그리고 그 패턴이 반복되는 횟수를 나타내는 정수 $k_i$ ($1 \le k_i \le 100000$). 각 설명에서 모든 $l_i$의 합은 $10000$을 넘지 않는다.

두 설명이 같은 목걸이를 나타내면 TAK(폴란드어로 "예"), 그렇지 않으면 NIE(폴란드어로 "아니오")를 한 줄에 출력한다.