https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=44
O(N^4 + N^4 for pre-computation): https://www.ideone.com/UExbEQ
O(N^4 + N^2 for pre-computation): https://www.ideone.com/T9jbz0
O(N^3): https://www.ideone.com/9wqO1I