기상 증후군

21세기에는 많은 사람이 기상 증후군이라는 이상한 병에 걸렸다. 증상은 아침에 침대에서 일어나기가 매우 힘들고, 일어난 뒤에도 몸이 개운하지 않다는 것이다. 평소 활발한 십 대인 ATM도 기상 증후군 때문에 고생하고 있다. 끊임없는 연구 끝에 그는 이 병의 원인을 알아냈다. 태평양의 드넓은 해저에는 DRD라는 거대한 용이 살고 있는데, 이 용은 잠의 정수를 지니고 있어서 원하는 대로 모든 사람의 잠자는 시간을 늘릴 수 있다. 그래서 DRD가 움직일 때마다 모든 사람의 기상 증후군이 심해지고, 그 속도는 무서울 정도로 빨라서 점점 더 많은 사람이 이 병에 걸리고 있다. 이 끔찍한 병을 끝내기 위해 ATM은 태평양 해저로 가서 이 악한 용을 완전히 죽이기로 결심했다.

수많은 고난 끝에 ATM은 마침내 DRD가 쉬고 있는 곳에 도착했다. 이제 그는 앞에 놓인 힘든 싸움을 준비한다. DRD는 아주 특별한 전술을 쓴다. 그의 방어선은 일련의 계산으로 상대의 공격력을 변환시켜 자신이 받는 피해를 최소화한다. 대략적으로 말해, DRD의 방어선은 n개의 방어문으로 이루어져 있다. 각 방어문에는 연산자 op와 매개변수 t가 있다. 연산자는 반드시 OR, XOR, AND 중 하나이고, 매개변수는 반드시 음이 아닌 정수이다. 방어문을 지나기 전의 공격력이 x라면, 방어문을 지난 뒤의 공격력은 x op t이다. 마지막으로 DRD가 받는 피해는, 상대의 처음 공격력 x가 모든 n개의 방어문을 지난 뒤의 값이다.

ATM은 실력이 부족해서, 공격의 처음 공격력은 0과 m 사이의 정수만 될 수 있다(0, 1, …, m 중 아무 값이나 처음 공격력으로 고를 수 있다). 하지만 방어문을 지난 뒤의 최종 공격력은 m에 제한되지 않는다. 기운을 아끼기 위해, 그는 DRD에게 입히는 피해를 최대로 만들 최적의 처음 공격력을 골라야 한다. 한 번의 공격으로 DRD에게 얼마나 피해를 입힐 수 있는지 계산하도록 도와주자.

첫째 줄에 두 정수 n과 m이 주어진다. 이는 DRD가 n개의 방어문을 사용하고, ATM이 0과 m 사이의 정수를 처음 공격력으로 고를 수 있음을 뜻한다.

다음 n개의 줄은 각각 방어문 하나를 설명한다. 각 줄은 op를 나타내는 문자열, 공백, 그리고 그 방어문의 매개변수인 음이 아닌 정수 t로 이루어진다.​​​​​​​

한 줄에 정수 하나를 출력한다. 이는 ATM이 한 번의 공격으로 DRD에게 입힐 수 있는 최대 피해이다.

• 2 ≤ n ≤ 105
• 2 ≤ m ≤ 109
• 0 ≤ t ≤ 109 
• op는 OR, XOR, AND 중 하나