시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 38 11 10 29.412%

문제

월쉬 행렬이란 행렬의 크기가 2의 제곱이며, 행렬의 원소가 +1 또는 -1인 정사각형 행렬이다.

이 행렬의 가장 큰 특징은 임의의 두 행(또는 열)의 스카라 곱이 0인 것이다.

아래는 처음 셋 월쉬 행렬이다. (회색 선은 보기 편하게 하기 위해 그은 것)

크기가 2N+1인 월쉬 행렬은 크기가 2N인 4개의 월쉬 행렬을 합쳐서 만들 수 있다. 오른쪽 아래 행렬은 다른 세 행렬과 다르게 모든 원소를 반전시켜서 넣어야 한다.

월쉬 행렬의 행의 번호를 위에서 부터 0번이라고 하고, 열의 번호는 왼쪽에서 부터 0이라고 하자. 이때 N, R, S, E가 주어졌을 때, 크기가 2N인 월쉬 행렬에서 R행 S열부터 R행 E열까지 합을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 네 정수 N, R, S, E로 이루어져 있다. (0 ≤ N ≤ 60, 0 ≤ R < 2N, 0 ≤ S ≤ E < 2N, E − S ≤ 10,000)

마지막 줄에는 -1이 4개 주어진다.

출력

각 테스트 케이스에 대해서 정답을 출력한다.

예제 입력 1

2 1 0 1
48 0 0 47
-1 -1 -1 -1

예제 출력 1

0
48

힌트

W3sicHJvYmxlbV9pZCI6IjQ5MDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZDRcdWMyNmMgXHVkNTg5XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM2ZDRcdWMyNmMgXHVkNTg5XHViODJjXHVjNzc0XHViNzgwJm5ic3A7XHVkNTg5XHViODJjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCAyXHVjNzU4IFx1YzgxY1x1YWNmMVx1Yzc3NFx1YmE3MCwgXHVkNTg5XHViODJjXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YWMwMCArMSBcdWI2MTBcdWIyOTQgLTFcdWM3NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDU4OVx1YjgyY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0IFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1ZDJiOVx1YzlkNVx1Yzc0MCBcdWM3ODRcdWM3NThcdWM3NTggXHViNDUwIFx1ZDU4OShcdWI2MTBcdWIyOTQgXHVjNWY0KVx1Yzc1OCBcdWMyYTRcdWNlNzRcdWI3N2MgXHVhY2YxXHVjNzc0IDBcdWM3NzggXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM1NDRcdWI3OThcdWIyOTQgXHVjYzk4XHVjNzRjIFx1YzE0YiBcdWM2ZDRcdWMyNmMgXHVkNTg5XHViODJjXHVjNzc0XHViMmU0LiAoXHVkNjhjXHVjMGM5IFx1YzEyMFx1Yzc0MCBcdWJjZjRcdWFlMzAgXHVkM2I4XHVkNTU4XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhZGY4XHVjNzQwIFx1YWM4Myk8XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC93YWwucG5nXCIgc3R5bGU9XCJ3aWR0aDogNTM0cHg7IGhlaWdodDogOTFweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkMDZjXHVhZTMwXHVhYzAwIDI8c3VwPk4rMTxcL3N1cD5cdWM3NzggXHVjNmQ0XHVjMjZjIFx1ZDU4OVx1YjgyY1x1Yzc0MCBcdWQwNmNcdWFlMzBcdWFjMDAgMjxzdXA+TjxcL3N1cD5cdWM3NzggNFx1YWMxY1x1Yzc1OCBcdWM2ZDRcdWMyNmMgXHVkNTg5XHViODJjXHVjNzQ0IFx1ZDU2OVx1Y2NkMFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWQ1ODlcdWI4MmNcdWM3NDAgXHViMmU0XHViOTc4IFx1YzEzOCBcdWQ1ODlcdWI4MmNcdWFjZmMgXHViMmU0XHViOTc0XHVhYzhjIFx1YmFhOFx1YjRlMCBcdWM2ZDBcdWMxOGNcdWI5N2MgXHViYzE4XHVjODA0XHVjMmRjXHVjZjFjXHVjMTFjIFx1YjEyM1x1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvd2FsMi5wbmdcIiBzdHlsZT1cIndpZHRoOiAyMjlweDsgaGVpZ2h0OiA2MXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2ZDRcdWMyNmMgXHVkNTg5XHViODJjXHVjNzU4IFx1ZDU4OVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YmQ4MFx1ZDEzMCAwXHViYzg4XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1YWNlMCwgXHVjNWY0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHViZDgwXHVkMTMwIDBcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM3NzRcdWI1NGMgTiwgUiwgUywgRVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWQwNmNcdWFlMzBcdWFjMDAgMjxzdXA+TjxcL3N1cD5cdWM3NzggXHVjNmQ0XHVjMjZjIFx1ZDU4OVx1YjgyY1x1YzVkMFx1YzExYyBSXHVkNTg5IFNcdWM1ZjRcdWJkODBcdWQxMzAgUlx1ZDU4OSBFXHVjNWY0XHVhZTRjXHVjOWMwIFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViMTI0IFx1YzgxNVx1YzIxOCBOLCBSLCBTLCBFXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuICgwICZsZTsgTiAmbGU7IDYwLCAwICZsZTsgUiAmbHQ7IDI8c3VwPk48XC9zdXA+LCAwICZsZTsgUyAmbGU7IEUgJmx0OyAyPHN1cD5OPFwvc3VwPiwgRSAmbWludXM7IFMgJmxlOyAxMCwwMDApPFwvcD5cclxuPHA+XHJcblx0XHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAtMVx1Yzc3NCA0XHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjODE1XHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0OTA3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSSBTcGVhayBXaGFsZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkFjY29yZGluZyB0byBXaWtpcGVkaWEsIGEgV2Fsc2ggbWF0cml4IGlzIGEgc3BlY2lcdWZiMDFjIHNxdWFyZSBtYXRyaXgsIHdpdGggZGltZW5zaW9ucyBlcXVhbCB0byBhIHBvd2VyIG9mIDIsIHRoZSBlbnRyaWVzIG9mIHdoaWNoIGFyZSArMSBvciAmbWludXM7MSwgYW5kIHRoZSBwcm9wZXJ0eSB0aGF0IHRoZSBkb3QgcHJvZHVjdCBvZiBhbnkgdHdvIGRpc3RpbmN0IHJvd3MgKG9yIGNvbHVtbnMpIGlzIHplcm8uIEJlbG93IGFyZSB0aGUgXHVmYjAxcnN0IHRocmVlIFdhbHNoIE1hdHJpY2VzLiAoVGhlIGdyYXkgbGluZXMgYXJlIGltYWdpbmFyeSBsaW5lcyBmb3IgaWxsdXN0cmF0aW9uIHB1cnBvc2Ugb25seS4pPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvd2FsLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjkxcHg7IHdpZHRoOjUzNHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkEgV2Fsc2ggTWF0cml4IG9mIHNpemUgMjxzdXA+TisxPFwvc3VwPiBjYW4gYmUgY29uc3RydWN0ZWQgYXMgdGhlICZsZHF1bzt1bmlvbiZyZHF1bzsgb2YgNCBXYWxzaCBNYXRyaWNlcyBvZiBzaXplIDI8c3VwPk48XC9zdXA+IGFycmFuZ2VkIHN1Y2ggdGhhdCB0aGUgbG93ZXIgcmlnaHQgbWF0cml4IGlzIGludmVydGVkIHdoZXJlYXMgdGhlIG90aGVyIDMgbWF0cmljZXMgYXJlIG5vdCwgaS5lLjo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC93YWwyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjYxcHg7IHdpZHRoOjIyOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkxldCZyc3F1bztzIG51bWJlciB0aGUgcm93cyBvZiBhIGdpdmVuIFdhbHNoIE1hdHJpeCBmcm9tIHRoZSB0b3Agc3RhcnRpbmcgd2l0aCByb3cgMC4gU2ltaWxhcmx5LCBsZXQmcnNxdW87cyBudW1iZXIgdGhlIGNvbHVtbnMgb2YgdGhlIG1hdHJpeCBmcm9tIHRoZSBsZWZ0IHN0YXJ0aW5nIHdpdGggY29sdW1uIDAuIEdpdmVuIHRoZSBmb3VyIGludGVnZXJzIE4sIFIsIFMsIGFuZCBFLCB3cml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGNvbnN0cnVjdCBhIFdhbHNoIE1hdHJpeCBvZiBzaXplIDI8c3VwPk48XC9zdXA+IGFuZCB3aWxsIHByaW50IHRoZSBzdW0gb2YgYWxsIHRoZSBudW1iZXJzIGluIHJvdyAjUiBiZXR3ZWVuIGNvbHVtbnMgI1MgYW5kICNFIChpbmNsdXNpdmUuKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIHdpbGwgYmUgdGVzdGVkIG9uIG9uZSBvciBtb3JlIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGlzIHNwZWNpXHVmYjAxZWQgdXNpbmcgYSBzaW5nbGUgbGluZSBsaXN0aW5nIGZvdXIgaW50ZWdlcnMgaW4gdGhlIGZvbGxvd2luZyBvcmRlcjogTiwgUiwgUywgYW5kIEUsIHdoZXJlIDAgJmxlOyBOICZsZTsgNjAsIDAgJmxlOyBSICZsdDsgMjxzdXA+TjxcL3N1cD4sIDAgJmxlOyBTICZsZTsgRSAmbHQ7IDI8c3VwPk48XC9zdXA+LCBhbmQgRSAmbWludXM7IFMgJmxlOyAxMCwwMDAuPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGhhcyBmb3VyIC0xJnJzcXVvO3MgYW5kIGlzIG5vdCBwYXJ0IG9mIHRoZSB0ZXN0IGNhc2VzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIG91dHB1dCBvbiBhIHNpbmdsZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==