
ZOJ Problem Set  3995
We define a string of length \(l\) as an array \(S[1..l]\). All the elements within it belongs to a finite set \(\sum=\{a,b,...,z\}\). Let \(\text{Prefix}(S,i)=S[1..i]\) be one prefix of \(S\) with a length of \(i\). Similarly, \(\text{Suffix}(S,j)=S[j..l]\) denotes one \(S\)'s suffix of length \(lj+1\). Now DreamGrid gives you a string multiset \(\{S_{n}\}\) with the cardinality of \(n\), and \(q\) not so hard tasks: For every task, you will receive two integers \(i, j\) (\(i \ne j\)) denoting the \(i\)th and the \(j\)th string in the aforementioned multiset. You have to calculate the longest string \(S^{'}\) which satisfies the following two conditions at the same time.
If such \(S^{'}\) doesn't exist, you have to print a character 'N'(without quotes). Otherwise your program should print \(\{S_{k}\}\) in one line. InputThere are about 10 test cases. For every test case, the first line contains an integer \(n\) (\( 1 \le n \le 10^5\)). The next \(n\) lines each contains a lowercased string \(S_{i}\). We guarantee that \(1 \le \sum_{i=1}^{n}S_{i}\le 5\times 10^5\) and each string is not empty. The next line contains an integer \(q\) (\(1 \le q \le 10^5\)). And the final \(q\) lines each contains two integers \(i, j\) (\(1 \le i, j \le n\), \(i \ne j\)). OutputFor every query, print the answer as the description narrates. Sample Input3 ab cb de 2 1 2 2 3 7 xabcd yabcd cdo cdp cdq cdr abcdz 1 1 2 3 aa aa aa 1 1 3 Sample OutputN N 1 3 Author: TANG, Xiaohu Source: ZOJ Monthly, January 2018 