对于两个字符串 $A = a_1a_2\cdots a_n$ 和 $B = b_1b_2\cdots b_m$，定义其最长公共前缀长度 $\text{LCP}(A, B)$ 如下：
$$\text{LCP}(A,B)=\max {k|0\le k\le n,k\le m,a_1a_2\cdots a_k=b_1b_2\cdots b_k}$$
给定 n 个由小写字母组成的两两不同的非空字符串 $S_1, S_2, \cdots , S_n$，对于一个 $1$ 到 $n$ 的排列 $P = (p_1, p_2, \cdots , p_n)$，定义 $P$ 的价值 $W(P)$ 如下：
$$W(P)=\sum_{i=2}^n (\text{LCP}(S_{p_{i-1}},S_{p_i}))^2$$
我们设能够产生最大价值的排列为 $P_G^*$。
此外，还有 $q$ 个附加任务。对于第 $i$ 个任务，给定两个 $1$ 到 $n$ 之间的不同的整数 $X_i$ 和 $Y_i$。对于排列 $P$，若 $P$ 在满足 $W (P) = W (P_G^*)$ 的前提条件之下，同时满足第 $X_i$ 个字符串 $S_{X_i}$ 恰好排在第 $Y_i$ 个字符串 $S_{Y_i}$ 之前， 即 $\text{pos}(S_{X_i}) +1= \text{pos}(S_{Y_i})$，其中 $\text{pos}(S_i)$ 表示字符串 $S_i$ 在排列中的位置，则排列 $P$ 还将获得 $2^i$ 的奖励。所有任务的奖励之和称之为总任务奖励。
我们设能够使得总任务奖励最大的排列为 $P_B^*$。
试求：
1. $W(P_G^)$，即可能产生的最大价值；
2. $P_B^$，在保证最大价值前提下，可以使总任务奖励最大的排列。
LibreOJ