#1989. Far Away Song

    ID: 1989 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest4586来源:qoj.ac数据:公开样例字符串动态规划

Far Away Song

Far Away Song

题目描述

标题: Far Away Song - Problem - QOJ.ac

#21428. Far Away Song

Statistics

让我听听你的声音吧,告诉我你旅途中的故事——

无论快乐的事,还是痛苦的事,还有那些铭刻在心的相遇。

Far Away Song - anemoi

题目描述

给定一个长度为 n 的字符串 S,下标从 1 开始。记 S(i,j)=SiSi+1⋯Sj,表示 S 从第 i 个字符到第 j 个字符组成的子串。

若非空字符串 B 同时是字符串 X 的前缀和后缀,且 |B|<|X|,则称 B 是 X 的一个 Border,其中 |X| 表示字符串 X 的长度。

初始时,你位于子串 S(1,n)。每次跳跃按如下方式进行:

  1. 在当前所在的子串中选择一个子串 X。
  2. 选择 X 的一个 Border B,要求 2|B|≥|X|。
  3. 跳到 B 在 X 中作为前缀或后缀所对应的子串上,两者任选其一。

例如,当 S 为 aabaaba,你位于 S(1,7) 时,可以选择 X=S(2,7)= abaaba。它的 Border aba 的长度恰好是 |X| 的一半,因此你可以跳到 S(2,4) 或 S(5,7)。

对于每个 1≤i≤n,请分别求出从 S(1,n) 出发、最终到达 S(i,i) 时,最多可以进行多少次跳跃。若无法到达,则答案为 −1。允许不进行任何跳跃。

多组测试数据。

输入格式

第一行包含一个整数 T,表示测试数据组数。

接下来依次输入每组测试数据,对于每组测试数据,输入一行,表示字符串 S。

输出格式

对于每组测试数据,输出一行,包含 n 个整数,第 i 个整数表示 S(i,i) 的答案(若无法到达 S(i,i),请输出 -1)。

样例 1

输入

5
abbababbab
bbabbaabbabbaaabab
babbaaaaabaabaaabaaba
baabaabaabaacaabaabaabaacaabaabaabaac
bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba

输出

-1 2 2 -1 -1 -1 2 2 -1 -1
3 3 -1 3 3 2 2 3 3 -1 3 3 2 2 2 -1 -1 -1
-1 -1 1 1 4 4 4 4 4 -1 3 3 -1 3 3 3 -1 3 3 -1 -1
-1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1
1 1 2 2 -1 4 4 4 4 4 6 6 6 6 6 6 6 -1 -1 -1 -1 3 3 -1 3 3 -1 3 3 1 1 -1 -1 -1 -1 -1 2 3 3 -1 3 3 -1 3 3 -1 3 3 2 -1

解释

第一组数据中,S= abbababbab,它的长度为 5 的前缀和后缀均为 abbab。可以进行以下两次跳跃:

  • 先跳到 S(1,5),再选择 S(2,3)= bb,跳到 S(2,2) 或 S(3,3)。
  • 先跳到 S(6,10),再选择 S(7,8)= bb,跳到 S(7,7) 或 S(8,8)。

只有第一次跳到上述两个 abbab 时,才能继续跳跃,而下一次跳跃只能到达单个字符,因此这四个位置的最大跳跃次数均为 2。

其余位置均无法通过跳跃到达,故答案为 −1。

样例 2

见附件中 wind2.in 和 wind2.ans。此样例满足子任务 3 的约束条件。

样例 3

见附件中 wind3.in 和 wind3.ans。此样例满足子任务 5 的约束条件。

样例 4

见附件中 wind4.in 和 wind4.ans。此样例满足子任务 6 的约束条件。

样例 5

见附件中 wind5.in 和 wind5.ans。此样例满足子任务 8 的约束条件。

数据范围

本题开启合理的子任务依赖。

子任务 n≤ ∑n≤ 特殊性质 分值 1 18 500 无 5 2 500 14 3 5×103 5×103 21 4 105 105 18 5 2×105 2×105 A 15 6 B 13 7 C 2 8 无 12

特殊性质 A:存在非空字符串 P,使得 S 是无限循环串 P∞ 的前缀,且 |P|≤10。

特殊性质 B:S 随机生成,即 S 的每个字符在大小 ≥2 的字符集中均匀随机。

特殊性质 C:对于所有 1≤i<n,均有 Si≠Si+1。

对于所有数据,保证 1≤n≤2×105,且单个测试点内所有测试数据的字符串长度之和 ∑n≤2×105。字符串 S 仅包含小写英文字母。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5
abbababbab
bbabbaabbabbaaabab
babbaaaaabaabaaabaaba
baabaabaabaacaabaabaabaacaabaabaabaac
bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba
-1 2 2 -1 -1 -1 2 2 -1 -1
3 3 -1 3 3 2 2 3 3 -1 3 3 2 2 2 -1 -1 -1
-1 -1 1 1 4 4 4 4 4 -1 3 3 -1 3 3 3 -1 3 3 -1 -1
-1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1
1 1 2 2 -1 4 4 4 4 4 6 6 6 6 6 6 6 -1 -1 -1 -1 3 3 -1 3 3 -1 3 3 1 1 -1 -1 -1 -1 -1 2 3 3 -1 3 3 -1 3 3 -1 3 3 2 -1

样例 2

9
abbbaaba
aaabbaaaaba
abbbaabaabaaabba
bbbbabbabaabbaaaabaaaaa
bbbbabbaabbabbbbabbaabbbbbbbabb
bbbbbbbbbbbaaaacccccccabbbaabaabaaabb
baabaaaaaabbbaaabbbbbbbaaabababbaabaabbbaab
aaaaaaabbabbbbabbaaaaaaaaababaaabababbabbbaabbaaabbbbbabaab
aabbbbbbaabababaabbaaaaaaabbbbbaaaaaaabbbbbaaaaaaabbbbbaaaaaaabbbbbaaaaaaabbbbbaaaaaaabbbbbaaaaaaabbaaabbbbbbbbbbbbbbaaaaabbbbbbbbbbbbbbaaaaabbbbbbbbbbbbbbaaaaabbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaabbbbbbbcccccccccccccccccccccccccccccccccccccccaaaaaaccccccccccccccbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbaabaabaaabbabbbaaabbabbbaaabbabbabbbaabbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbbccccccccccaaaabbbbbbbbbbbbbcccccccccbbbbbbbbbbbbbbbbbaaabbbaaabbbaaabbbaaabbbaaabbbaaabbbaaacdddccdccdcccddcdddcccddcdddcccddcddcdddccdcccdddccdccdcccddcddcdddccdcccdddccdccdcccddcddcdddccdcccdddccdcccdddccdccdcccddcdddcccddcddcdddccdccdcccddcdddcccddcdddcccddcddcdddccdcccdddccdcccdddccdccdcccddcdddcccddcddcdddccdccdcccddcdddcccddcdddcababaaaaaaaababbababbbbaabbaaabbabaababbbbaaaabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcdddccdccdcccddcdddcccddcdddcccddcddcdddccdcccdddccdccdcccddcddcdddccdcccdddccdccdcccddcddcdddccdcccdddccdcccdddccdccdcccddcdddcccddcddcdddccdccdcccddcdddcccddcdddcccddcddcdddccdcccdddccdcccdddccdccdcccddcdddcccddcddcdddccdccdcccddcdddcccddcdddcccddcdbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbabbbabbbbbbabbabbbabbcbbbabbabbbabbbbbbabbabbbabbbbbbabbabbbabbbbbbabbabbbabbcbbbabbabbbabbbbbbabbabbbabbabbbabbabbbabbbbbbabbabbbabbcbbbabbabbbabbbbbbabbabbbabbbbbbabbabbbabbbbbbabbabbbabbcbbbabbabbbabbbbbbabbabbbabbababababbbabbaababbbbbbaabbbbbbcabbbbbbaabbbbbbbbbbbbaaabaaaabbbaaabaaaaaaabaababababbaabbababbbabbbbbbbaaaaabbbababbbbbaaababbababbabaabbababaabbbbabbbabaabaaabaaaabaababbabbaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaabbabaabbaabbabaabbaabbabaabbaabbabaabbaabbabaabbaabbabaabbaabbabaaabbbaabaabaaabbabbbaaabbabbbaaabbabbabbabbbaabaabaaabbabbbaaabbabbbaaabbabbabbbaabaaabbbaabaabaaabbabbabbbaabaaabbbaabaabaaabbabbabbbaabaaabbbaabaaabbbaabaabaaabbabbbaaabbabbabbbaabaabababbaababbabbbaabbababaabbbbabbbbabbababaaaabbbbabaababbbaabbbbbababaabbbbbaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbaabbbbbbbbaaaaaaaaaaaaaabbbbbbbbbbbcccccccccccaababbaababbaababbaababbaababbaababbaababbaababbaaabbabaaaaabbababaaabbabaaaaabbababaaabbabaaaaabbababaaabbabaaaaabbabaaabaaabaabaaabaaabaabcaabaaabaabaaabaaabaabbaabaaabaabaaabaaabaabcaabaaabaabaaabaaabaabbaabaaabaabaaabaaabaabcaabaaabaabaaabaaabaabbaabaaabaabaaabaaabaabcaabaaabaabaaabaaabaababbbaabaabaaabbabbbaaabbabbbaaabbabbabbbaabaaabbbaabaabaaabbabbabbbaabaaabbbaabaabaaabbabbabbbaabaaabbbaabaaabbbaabaabaaabbabbbaaabbabbabbbaabaaaaaaaaaaaaaaacccccccccccccccccccccccccccccbbbbbbbbbbbbbbbbbbbbbbbbbbbbcccccccdddccdccdcccddcdddcccddcdddcccddcddcdddccdcccdddccdccdcccddcddcdddccdcccdddccdccdcccddcddcdddccdcccdddccdcccdddccdccdcccddcdddcccddcddcdddccdccdcccddcdddcccddcdddcccddcddcdddccdcccdddccdcccdddccdccdcccddcdddcccddcbbaaaaabbbbbbbaaaaaaaaabbaaaaabbbbbbbaaaaaaaaabbaaaaabbbbbbbaaaaaaaaabbaaaaabbbbbbbaaaaaaaaabbaaaaabbbbbbbaaaaaaaaabbaaaaabbbbbbbaaaaaaaaabbaaaaabbbbbbbaaaaaaaaabbaaaaabbbbbbbaaaaaaaaabbaaaaabbbbbbbaaaaaaaaabbaaaaabbbbbbbaaaaaaaaabbaaaaabbbbbbbaaaaaaaaabbaaaabbabbabbabbabbbabbabbabbabbbabbabbabbabbbabbabbabbabbbabbabbabbabccbbbbbbbbbbbbbbbbcccccccccaaaaaaaaaaaaaaaaaaaaaacdddccdccdcccddcdddcccddcdddcccddcddcdddccdcccdddccdccdcccddcddcdddccdcccdddccdccdcccddcddcdddccdcccdddccdcccdddccdccdcccddcdddcccddcddcdddccdccdcccddcdddcccddcdddcccddcddcdddccdcccdddccdcccdddccdccdcccddcdddcccddcddcdddccdccdcccddcdddcccddcdddcccddcddabbbaabaabaaabbabbbaaabbabbbaaabbabbabbbaabaaabbbaabaabaaabbabbabbbaabbbbbbbbbbaabbbbbaaaaaaabbbbbbcccccccccccccccccaaaaaabaaaaaababaaaabbbabbaabaaabbbabbabbbabaabbabbabababbbbbbababbbbbbababbbbbbababbbbabababbbbbbababbbbbbababbbbbbababbbbbbababbbbbbababbbbbbababbbbbbababbbbabababbbbbbababbbbbbababbbbbbababbbbbabaabbbbbbaaaababbaabbabbbbaaabababaaaabbbbbaabbaabaaaabbbbbaabbbbaabbaaabbbbaababaaaabaabaabbaaabbabbaabaabababababbabbbbbbbaaabbbaabaaabbbaabaabbbbaaabbbaababbaabbabbbaaaaaabaabaabaabbbababbbababbbababbbbabbaaabbbabbbbabaabababbbaabaabaaabbbaaabbbbbbaaabbbbbbbabaaabbaaabcaaabbaaabcaaabbaaabcaaabbaaabbaaabbaaabcaaabbaaabcaaabbaaabcaaabbaaababbbaabaabaaabbabbbaaabbabbbaaabbabbabbbaabaaabbbaabaabaaabbabbabbbaabaaabbbaabaabaaabbabbabbbaabaaabbbaabaaabbbaabaabaaabbabbbaaabbabbabbbaabaabaaabbabbbaaabbabbbaaabbabbabbbaabaaabbbaabaaabbbaabaaaaabbbbbbbaaaaaaaaabbbbbbbaaaaabbbbbbbaaaaaaa
-1 2 2 2 1 1 -1 -1
2 2 2 1 1 3 3 3 3 -1 -1
-1 2 2 2 3 3 -1 3 3 -1 3 3 2 1 1 -1
3 3 3 3 -1 2 2 -1 -1 1 1 1 1 4 4 4 4 -1 4 4 4 4 4
3 3 3 3 -1 2 2 1 1 2 2 -1 3 3 3 3 -1 2 2 1 1 6 6 6 6 6 6 6 -1 1 1
10 10 10 10 10 10 10 10 10 10 10 3 3 3 3 6 6 6 6 6 6 6 -1 2 2 2 3 3 -1 3 3 -1 3 3 2 1 1
-1 2 2 -1 5 5 5 5 5 5 3 3 3 3 3 3 6 6 6 6 6 6 6 2 2 2 -1 -1 -1 -1 1 1 2 2 -1 2 2 2 2 2 1 1 -1
6 6 6 6 6 6 6 2 2 -1 3 3 3 3 -1 2 2 8 8 8 8 8 8 8 8 8 -1 -1 -1 3 3 3 -1 -1 -1 -1 2 2 -1 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 -1 -1 1 1 -1
1 1 5 5 5 5 5 5 1 1 -1 -1 -1 -1 -1 1 1 6 6 11 11 11 11 11 11 11 9 9 9 9 9 11 11 11 11 11 11 11 9 9 9 9 9 11 11 11 11 11 11 11 9 9 9 9 9 11 11 11 11 11 11 11 9 9 9 9 9 11 11 11 11 11 11 11 9 9 9 9 9 11 11 11 11 11 11 11 9 9 9 9 9 11 11 11 11 11 11 11 6 6 4 4 4 15 15 15 15 15 15 15 15 15 15 15 15 15 15 6 6 6 6 6 15 15 15 15 15 15 15 15 15 15 15 15 15 15 6 6 6 6 6 15 15 15 15 15 15 15 15 15 15 15 15 15 15 6 6 6 6 6 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 10 10 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 10 10 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 10 10 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 10 10 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 10 10 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 10 10 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 10 10 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 10 10 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 10 10 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 10 10 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 6 6 6 6 6 6 6 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 5 5 5 5 5 5 13 13 13 13 13 13 13 13 13 13 13 13 13 13 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 -1 3 3 3 3 3 -1 3 3 -1 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 -1 3 3 3 2 2 14 14 14 14 14 14 14 14 14 14 14 14 14 14 2 2 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 9 9 9 9 9 9 9 9 9 9 3 3 3 3 12 12 12 12 12 12 12 12 12 12 12 12 12 8 8 8 8 8 8 8 8 8 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 -1 2 2 2 3 3 -1 3 3 -1 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 3 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 4 4 4 4 4 -1 4 4 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 -1 -1 -1 -1 -1 7 7 7 7 7 7 7 7 -1 -1 2 2 -1 -1 -1 3 3 3 3 2 2 2 2 2 2 2 2 2 -1 -1 1 1 -1 -1 3 3 3 3 3 3 3 3 3 3 3 -1 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 -1 2 2 2 3 3 -1 3 3 -1 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 3 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 4 4 4 4 4 -1 4 4 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 4 4 4 3 3 -1 -1 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 139 -1 4 4 -1 4 4 4 -1 7 7 7 7 7 7 -1 4 4 -1 4 4 4 -1 4 4 -1 5 5 5 -1 5 5 -1 6 6 6 -1 8 8 8 8 8 8 -1 5 5 -1 6 6 6 -1 8 8 8 8 8 8 -1 5 5 -1 6 6 6 -1 8 8 8 8 8 8 -1 5 5 -1 5 5 5 -1 5 5 -1 3 3 3 -1 3 3 -1 4 4 4 -1 6 6 6 6 6 6 -1 4 4 -1 4 4 4 -1 4 4 -1 4 4 4 -1 4 4 -1 4 4 4 -1 6 6 6 6 6 6 -1 3 3 -1 3 3 3 -1 3 3 -1 5 5 5 -1 5 5 -1 6 6 6 -1 8 8 8 8 8 8 -1 5 5 -1 6 6 6 -1 8 8 8 8 8 8 -1 5 5 -1 6 6 6 -1 8 8 8 8 8 8 -1 5 5 -1 5 5 5 -1 5 5 -1 3 3 3 -1 3 3 -1 4 4 4 -1 6 6 6 6 6 6 -1 4 4 -1 4 4 4 -1 4 4 -1 -1 -1 -1 -1 -1 -1 2 2 2 -1 2 2 1 1 -1 -1 5 5 5 5 5 5 1 1 5 5 5 5 5 5 -1 -1 5 5 5 5 5 5 1 1 11 11 11 11 11 11 11 11 11 11 11 11 4 4 4 -1 4 4 4 4 3 3 3 4 4 4 -1 6 6 6 6 6 6 6 -1 2 2 -1 -1 -1 -1 -1 -1 2 2 1 1 2 2 -1 -1 -1 3 3 3 -1 6 6 6 6 6 6 6 4 4 4 4 4 2 2 2 -1 -1 -1 4 4 4 4 4 2 2 2 -1 -1 2 2 -1 -1 -1 2 2 -1 -1 1 1 2 2 -1 -1 -1 -1 1 1 3 3 3 3 -1 3 3 3 -1 -1 2 2 -1 3 3 3 -1 3 3 3 3 -1 2 2 -1 -1 2 2 -1 2 2 3 3 3 -1 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 8 8 8 8 8 8 -1 -1 8 8 8 8 8 8 8 8 -1 -1 8 8 8 8 8 8 8 8 -1 -1 8 8 8 8 8 8 8 8 -1 -1 8 8 8 8 8 8 8 8 -1 -1 8 8 8 8 8 8 8 8 -1 -1 8 8 8 8 8 8 8 8 -1 -1 7 7 2 3 3 3 4 4 -1 4 4 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 -1 4 4 3 4 4 -1 4 4 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 3 4 4 4 4 4 -1 4 4 -1 3 3 3 3 3 -1 3 3 2 3 3 3 3 3 -1 3 3 -1 3 3 2 2 2 -1 2 2 -1 -1 -1 -1 2 2 1 1 -1 -1 2 2 -1 2 2 2 1 1 1 1 -1 -1 -1 -1 1 1 4 4 4 4 -1 4 4 4 4 -1 2 2 -1 -1 -1 -1 3 3 3 3 3 3 3 3 -1 -1 1 1 -1 -1 2 2 2 1 1 4 4 4 4 4 -1 -1 -1 -1 1 1 4 4 4 4 4 4 4 4 4 -1 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 93 8 8 8 8 8 8 8 8 2 2 8 8 8 8 8 8 8 8 13 13 13 13 13 13 13 13 13 13 13 13 13 13 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 8 8 -1 -1 8 8 8 8 -1 -1 8 8 8 8 -1 -1 8 8 8 8 -1 -1 8 8 8 8 -1 -1 8 8 8 8 -1 -1 8 8 8 8 -1 -1 8 8 8 8 -1 -1 8 8 8 8 5 4 4 -1 -1 7 7 7 7 7 4 4 -1 -1 -1 -1 5 5 5 4 4 -1 -1 7 7 7 7 7 4 4 -1 -1 -1 -1 5 5 5 4 4 -1 -1 7 7 7 7 7 4 4 -1 -1 -1 -1 5 5 5 4 4 -1 -1 7 7 7 7 7 4 4 -1 -1 4 5 5 -1 5 5 5 -1 5 5 -1 5 5 5 -1 5 5 5 -1 5 5 -1 -1 5 5 -1 5 5 5 -1 5 5 -1 5 5 5 -1 5 5 5 -1 5 5 3 3 5 5 -1 5 5 5 -1 5 5 -1 5 5 5 -1 5 5 5 -1 5 5 -1 -1 5 5 -1 5 5 5 -1 5 5 -1 5 5 5 -1 5 5 5 -1 5 5 3 3 5 5 -1 5 5 5 -1 5 5 -1 5 5 5 -1 5 5 5 -1 5 5 -1 -1 5 5 -1 5 5 5 -1 5 5 -1 5 5 5 -1 5 5 5 -1 5 5 3 3 5 5 -1 5 5 5 -1 5 5 -1 5 5 5 -1 5 5 5 -1 5 5 -1 -1 5 5 -1 5 5 5 -1 5 5 -1 5 5 5 -1 5 5 5 -1 5 5 -1 -1 2 2 2 3 3 -1 3 3 -1 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 3 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 3 4 4 4 4 4 -1 4 4 -1 3 3 3 3 3 -1 3 3 2 3 3 3 3 3 -1 3 3 -1 3 3 2 2 2 -1 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 6 6 6 6 6 6 6 2 2 2 3 3 -1 3 3 -1 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 3 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 3 4 4 4 4 4 -1 4 4 -1 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 -1 3 3 3 4 4 -1 4 4 -1 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 -1 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 -1 3 3 2 2 2 -1 2 2 2 2 2 2 1 1 -1 11 11 14 14 14 14 14 16 16 16 16 16 16 16 18 18 18 18 18 18 18 18 18 11 11 14 14 14 14 14 16 16 16 16 16 16 16 18 18 18 18 18 18 18 18 18 11 11 14 14 14 14 14 16 16 16 16 16 16 16 18 18 18 18 18 18 18 18 18 11 11 14 14 14 14 14 16 16 16 16 16 16 16 18 18 18 18 18 18 18 18 18 11 11 14 14 14 14 14 16 16 16 16 16 16 16 18 18 18 18 18 18 18 18 18 11 11 14 14 14 14 14 16 16 16 16 16 16 16 18 18 18 18 18 18 18 18 18 11 11 14 14 14 14 14 16 16 16 16 16 16 16 18 18 18 18 18 18 18 18 18 11 11 14 14 14 14 14 16 16 16 16 16 16 16 18 18 18 18 18 18 18 18 18 11 11 14 14 14 14 14 16 16 16 16 16 16 16 18 18 18 18 18 18 18 18 18 11 11 14 14 14 14 14 16 16 16 16 16 16 16 18 18 18 18 18 18 18 18 18 11 11 14 14 14 14 14 16 16 16 16 16 16 16 18 18 18 18 18 18 18 18 18 11 11 13 13 13 13 8 8 -1 8 8 -1 8 8 -1 8 8 -1 7 8 8 -1 8 8 -1 8 8 -1 8 8 -1 7 8 8 -1 8 8 -1 8 8 -1 8 8 -1 7 8 8 -1 8 8 -1 8 8 -1 8 8 -1 7 8 8 -1 8 8 -1 8 8 -1 8 8 -1 -1 1 1 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 8 8 8 8 8 8 8 8 8 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 -1 2 2 2 3 3 -1 3 3 -1 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 3 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 2 2 2 3 3 -1 3 3 -1 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 -1 3 3 3 3 3 -1 3 3 2 3 3 3 3 3 -1 3 3 -1 3 3 2 3 3 -1 3 3 -1 3 3 2 1 1 9 9 9 9 9 9 9 9 9 9 2 2 5 5 5 5 5 6 6 6 6 6 6 6 5 5 5 5 5 5 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 6 6 6 6 6 6 -1 6 6 6 6 6 6 -1 -1 -1 3 3 3 3 2 2 2 -1 2 2 2 2 -1 2 2 2 2 2 2 -1 2 2 -1 2 2 2 -1 -1 1 1 2 2 -1 2 2 -1 -1 -1 -1 -1 8 8 8 8 8 8 -1 -1 -1 8 8 8 8 8 8 -1 -1 -1 8 8 8 8 8 8 -1 -1 -1 6 6 6 6 -1 -1 -1 -1 -1 11 11 11 11 11 11 -1 -1 -1 11 11 11 11 11 11 -1 -1 -1 11 11 11 11 11 11 -1 -1 -1 11 11 11 11 11 11 -1 -1 -1 11 11 11 11 11 11 -1 -1 -1 11 11 11 11 11 11 -1 -1 -1 11 11 11 11 11 11 -1 -1 -1 9 9 9 9 -1 -1 -1 -1 -1 8 8 8 8 8 8 -1 -1 -1 8 8 8 8 8 8 -1 -1 -1 8 8 8 8 8 8 -1 -1 -1 8 8 8 8 8 -1 -1 1 1 5 5 5 5 5 5 3 3 3 3 -1 -1 2 2 1 1 2 2 -1 3 3 3 3 2 2 2 -1 -1 -1 -1 -1 3 3 3 3 4 4 4 4 4 2 2 2 2 2 2 -1 3 3 3 3 4 4 4 4 4 2 2 4 4 4 4 2 2 2 2 2 2 2 3 3 3 3 1 1 -1 -1 -1 3 3 3 3 -1 3 3 -1 3 3 2 2 2 2 2 2 2 -1 2 2 2 2 -1 2 2 -1 -1 -1 -1 -1 -1 -1 -1 2 2 -1 6 6 6 6 6 6 6 3 3 3 3 3 3 3 3 -1 3 3 3 3 3 3 3 3 -1 3 3 3 3 3 3 2 2 2 2 2 2 1 1 -1 -1 2 2 1 1 2 2 -1 2 2 2 5 5 5 5 5 5 -1 4 4 -1 4 4 -1 4 4 4 4 4 -1 -1 -1 4 4 4 -1 -1 -1 4 4 4 -1 -1 -1 4 4 4 3 -1 2 2 2 2 2 3 3 3 -1 3 3 3 3 -1 -1 1 1 -1 -1 -1 -1 2 2 2 3 3 -1 3 3 -1 3 3 3 3 3 3 3 3 3 6 6 6 6 6 6 3 3 3 6 6 6 6 6 6 6 -1 -1 5 5 5 4 4 5 5 5 -1 -1 5 5 5 4 4 5 5 5 -1 -1 5 5 5 4 4 5 5 5 -1 -1 5 5 5 4 4 5 5 5 3 3 5 5 5 4 4 5 5 5 -1 -1 5 5 5 4 4 5 5 5 -1 -1 5 5 5 4 4 5 5 5 -1 -1 5 5 5 4 4 5 5 5 -1 -1 2 2 2 3 3 -1 3 3 -1 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 3 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 -1 4 4 4 5 5 -1 5 5 -1 5 5 5 5 5 -1 5 5 4 5 5 5 5 5 -1 5 5 3 4 4 4 4 4 -1 4 4 -1 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 -1 3 3 3 4 4 -1 4 4 -1 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 3 4 4 4 4 4 -1 4 4 -1 4 4 4 4 4 -1 4 4 4 4 4 4 4 4 -1 4 4 4 4 4 4 4 4 -1 5 5 5 5 5 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 7 7 7 7 7 7 7 5 5 5 5 5 7 7 7 7 7 7 7 6 6 6 6 6 6 6