힘 겨루기

서기 2045년, 세상은 어마무시하게 발전해서 엄청나게 힘이 강한 AI가 널리 보급되었다. 헬스를 열심히 하던 junie는 자신의 힘을 확인하기 위해서 코드네임 “TEST_SUBJECT_107”과 힘 겨루기를 하기로 했다.

힘 겨루기는 총 N개의 라운드로 구성되어있고, i라운드에 junie는 Ai의 힘을, TEST_SUBJECT_107는 Bi의 힘을 준다. 둘 다 K 이상의 힘을 버티지 못하기 때문에 지금까지 준 힘 (누적힘)이 K보다 크거나 같아지면 상대가 타격을 받고 게임이 종료된다. 또한 junie가 TEST_SUBJECT_107보다 많은 누적힘을 주고 그 차이가 50 이상이 되면 인간의 고등한 능력을 사용한 한판승으로 게임이 끝난다. 힘 겨루기의 승자는 후술할 규칙에 따라 결정된다.

junie는 TEST_SUBJECT_107를 못 이긴다는 생각에 비장의 필살기 "OverPower"를 준비했다. 이 필살기는 한 번만 사용할 수 있고, i번째 라운드에서 사용하면 junie가 Ai 대신 1.5Ai의 힘을 줄 수 있다. 그 값이 정수가 아닐 경우 정수로 버림한다. 하지만 이 필살기에는 부작용이 있어서, junie가 추가로 준 힘의 양만큼 다음 라운드에서 힘이 빠지게 된다. 그 결과로 음수의 힘을 줄 수도 있으며, 이것도 누적힘에 반영된다.

예를 들어서, 첫 번째 라운드에 10, 두 번째 라운드에 18의 힘을 주고, 첫 번째 라운드에서 OverPower를 사용한다고 하자. 그러면 첫 번째 라운드에서 15의 힘을 주고, 두 번째 라운드에서 5의 힘을 뺀 13의 힘을 주게 된다.

힘 겨루기의 승자는 다음과 같이 결정된다. 한 쪽만 상대에게 타격을 주었을 경우 그 쪽이 승리한다. 두 선수가 동시에 타격을 받으면 OverPower의 사용 유무에 따라 승패가 달라진다. OverPower를 사용했을 경우 TEST_SUBJECT_107의 승리가 되며, 사용하지 않았을 경우 junie의 승리가 된다. 두 선수가 동시에 타격을 받지 않고 한판승으로 게임이 끝날 경우 junie가 승리한다. N라운드가 끝날 때까지 아무도 타격을 주지 않고 한판승도 일어나지 않으면 무승부로 끝난다.

junie는 너무 똑똑해서 어떻게든 지지 않으려고 한다. 각 라운드마다 junie와 TEST_SUBJECT_107이 주는 힘이 주어질 때, 과연 힘 겨루기의 승자는 누가 될까?

메모리 제한에 유의하라.

N(1 ≤ N ≤ 400000)과 K(100 ≤ K ≤ 1000)이 주어진다

다음 줄부터 N개의 줄에 junie와 TEST_SUBJECT_107의 힘이 주어진다. 모든 힘은 0 이상 60 이하이다.

최종 승리자의 숫자를 출력한다.

junie의 승리는 1, TEST_SUBJECT_107의 승리는 -1, 무승부는 0을 출력한다.