34042번 - 천상도

문제

육도윤회에 따르면 호반우들은 생전의 행보에 따라 천상도, 수라도, 인간도, 축생도, 아귀도, 지옥도로 나뉘는 육도에서 다시 태어나며 깨달음을 얻어 윤회의 고리를 끊어야 한다.

천상도의 호반우들은 $M$개의 질문에 대답해야 한다. 각 질문은 $N$개의 정수 $a_{1}, a_{2}, \cdots , a_{N}$으로 이루어져 있으며, 호반우들은 이 중 1ドル$개 이상의 수를 선택하여 곱했을 때 나올 수 있는 가장 큰 수를 찾아야 한다.

호반우를 도와 천상도에서 깨달음을 얻어보자.

입력

첫째 줄에 $N$과 $M$이 주어진다. $(1 \leq N \leq 60 ; 1 \leq M \leq 20,000円)$

둘째 줄부터 $M$개의 줄에 걸쳐 각각의 질문에 해당하는 $N$개의 정수 $a_{1}, a_{2}, \cdots , a_{N}$이 공백을 두고 주어진다. $(-2 \leq a_{i} \leq 2)$

출력

$M$개의 줄에 걸쳐 각 질문마다 주어진 수 중 1ドル$개 이상의 수를 선택하여 곱했을 때 나올 수 있는 가장 큰 수를 출력한다.

제한

힌트