We basically have to find a string T without \(!\) in the beginning which is present in the set and after appending \(!\) in the beginning , the resulting string is also present in the set.

To do this we can maintain the set of input strings and for each string in the input we can check whether the corresponding string ( resulting string after removing \(!\) or after appending \(!\)) is also present in the set or not , If we do not find any such string then the answer is \(satisfiable\), else one of the possible answer is the obtained string in the previous step. The overall time complexity is \(O(N*\left|S_i\right|*logn)\) .

Sample Code (C++)