시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 74 26 20 44.444%

문제

상근 바게트에서 삼각 페스트리 N개를 구웠다. 모든 페스트리는 2차원 평면 위에서 정수 좌표 꼭짓점을 가지는 삼각형으로 나타낼 수 있다.

상근이의 말썽꾸러기 아들 정인이는 커다란 칼을 들고 페스트리를 자르려고 한다. 정인이는 좌표평면에서 수직 방향(x = c)이나 수평 방향(y = c)으로 칼질을 한다. 정인이가 칼질을 할 때, 총 몇 개의 페스트리가 잘리는지 구하려고 한다. 페스트리가 칼질로 두 부분으로 나누어졌을 때, 두 부분의 넓이가 0보다 크면 잘린 것이다.

페스트리의 위치와 정인이의 칼질이 주어졌을 때, 몇 개의 페스트리가 잘리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 페스트리의 개수 N이 주어진다. (2 ≤ N ≤ 100,000)

다음 N개 줄에는 106보다 작은 음이 아닌 정수 여섯 개가 주어진다. 정수는 순서대로 (x1, y1), (x2, y2), (x3, y3)이며, 삼각 페스트리를 이루는 세 꼭짓점이다. 세 점은 일직선 위에 있지 않다. 또, 페스트리는 겹치거나 접할 수도 있다.

다음 줄에는 정인이의 칼질의 수 M이 주어진다. (2 ≤ M ≤ 100 000)

다음 M개 줄에는 정인이가 어떻게 칼질을 하려고 하는지가 주어진다. 방정식 "x = c" 또는 "y = c"와 같은 형식으로 주어지며, c는 106보다 작은 음이 아닌 정수이다.

출력

첫째 줄에 입력으로 주어지는 정인이의 칼질이 페스트리 몇 개를 자르는지 출력한다. 모든 칼질은 독립적으로 생각하면 된다. 즉, 칼질을 하고 난 다음 페스트리가 마법처럼 붙는다고 생각하면 된다.

예제 입력 1

3
1 0 0 2 2 2
1 3 3 5 4 0
5 4 4 5 4 4
4
x = 4
x = 1
y = 3
y = 1

예제 출력 1

0
1
1
2
W3sicHJvYmxlbV9pZCI6IjU2MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzOThcdWMyYTRcdWQyYjhcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzBjMVx1YWRmYyBcdWJjMTRcdWFjOGNcdWQyYjhcdWM1ZDBcdWMxMWMgXHVjMGJjXHVhYzAxIFx1ZDM5OFx1YzJhNFx1ZDJiOFx1YjlhYyBOXHVhYzFjXHViOTdjIFx1YWQ2Y1x1YzZlMFx1YjJlNC4gXHViYWE4XHViNGUwIFx1ZDM5OFx1YzJhNFx1ZDJiOFx1YjlhY1x1YjI5NCAyXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjODE1XHVjMjE4IFx1Yzg4Y1x1ZDQ1YyBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NDQgXHVhYzAwXHVjOWMwXHViMjk0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YjlkMFx1YzM3ZFx1YWZiOFx1YjdlY1x1YWUzMCBcdWM1NDRcdWI0ZTQgXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1Y2VlNFx1YjJlNFx1Yjc4MCBcdWNlN2NcdWM3NDQgXHViNGU0XHVhY2UwIFx1ZDM5OFx1YzJhNFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWM3OTBcdWI5NzRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjODhjXHVkNDVjXHVkM2M5XHViYTc0XHVjNWQwXHVjMTFjIFx1YzIxOFx1YzljMSBcdWJjMjlcdWQ1YTUoeCA9IGMpXHVjNzc0XHViMDk4IFx1YzIxOFx1ZDNjOSBcdWJjMjlcdWQ1YTUoeSA9IGMpXHVjNzNjXHViODVjIFx1Y2U3Y1x1YzljOFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWNlN2NcdWM5YzhcdWM3NDQgXHVkNTYwIFx1YjU0YywgXHVjZDFkIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVkMzk4XHVjMmE0XHVkMmI4XHViOWFjXHVhYzAwIFx1Yzc5OFx1YjlhY1x1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQzOThcdWMyYTRcdWQyYjhcdWI5YWNcdWFjMDAgXHVjZTdjXHVjOWM4XHViODVjIFx1YjQ1MCBcdWJkODBcdWJkODRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViNDUwIFx1YmQ4MFx1YmQ4NFx1Yzc1OCBcdWIxMTNcdWM3NzRcdWFjMDAgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWJhNzQgXHVjNzk4XHViOWIwIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkMzk4XHVjMmE0XHVkMmI4XHViOWFjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWM4MTVcdWM3NzhcdWM3NzRcdWM3NTggXHVjZTdjXHVjOWM4XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVkMzk4XHVjMmE0XHVkMmI4XHViOWFjXHVhYzAwIFx1Yzc5OFx1YjlhY1x1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMzk4XHVjMmE0XHVkMmI4XHViOWFjXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IDEwPHN1cD42PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMTggXHVjNWVjXHVjMTJmIFx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzgxNVx1YzIxOFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgKHgxLCB5MSksICh4MiwgeTIpLCAoeDMsIHkzKVx1Yzc3NFx1YmE3MCwgXHVjMGJjXHVhYzAxIFx1ZDM5OFx1YzJhNFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjMTM4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc3NFx1YjJlNC4gXHVjMTM4IFx1YzgxMFx1Yzc0MCBcdWM3N2NcdWM5YzFcdWMxMjAgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyZTQuIFx1YjYxMCwgXHVkMzk4XHVjMmE0XHVkMmI4XHViOWFjXHViMjk0IFx1YWNiOVx1Y2U1OFx1YWM3MFx1YjA5OCBcdWM4MTFcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWM3NzhcdWM3NzRcdWM3NTggXHVjZTdjXHVjOWM4XHVjNzU4IFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBNICZsZTsgMTAwIDAwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjZTdjXHVjOWM4XHVjNzQ0IFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTRcdWM5YzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJjMjlcdWM4MTVcdWMyZGQgJnF1b3Q7eCA9IGMmcXVvdDsgXHViNjEwXHViMjk0ICZxdW90O3kgPSBjJnF1b3Q7XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBjXHViMjk0IDEwPHN1cD42PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1Yzc1OCBcdWNlN2NcdWM5YzhcdWM3NzQgXHVkMzk4XHVjMmE0XHVkMmI4XHViOWFjIFx1YmE4NyBcdWFjMWNcdWI5N2MgXHVjNzkwXHViOTc0XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViYWE4XHViNGUwIFx1Y2U3Y1x1YzljOFx1Yzc0MCBcdWIzYzVcdWI5YmRcdWM4MDFcdWM3M2NcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWNlN2NcdWM5YzhcdWM3NDQgXHVkNTU4XHVhY2UwIFx1YjA5YyBcdWIyZTRcdWM3NGMgXHVkMzk4XHVjMmE0XHVkMmI4XHViOWFjXHVhYzAwIFx1YjljOFx1YmM5NVx1Y2M5OFx1YjdmYyBcdWJkOTlcdWIyOTRcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NjI1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQlVSRUsiLCJkZXNjcmlwdGlvbiI6IjxwPkJha2VyIENydW1ibGUgaGFzIGp1c3QgYmFrZWQgTiB0cmlhbmd1bGFyIGJ1cmVrIHBhc3RyaWVzLiBFYWNoIHBhc3RyeSBjYW4gYmUgcmVwcmVzZW50ZWQgaW4gdGhlIENhcnRlc2lhbiBjb29yZGluYXRlIHN5c3RlbSBhcyBhIHRyaWFuZ2xlIHdpdGggdmVydGljZXMgaW4gaW50ZWdlciBjb29yZGluYXRlIHBvaW50cy48XC9wPlxyXG5cclxuPHA+VGhlIGJha2VyJiMzOTtzIG1pc2NoaWV2b3VzIHNvbiBKb2V5IGhhcyBqdXN0IHRha2VuIGEgbGFyZ2Uga25pZmUgYW5kIHN0YXJ0ZWQgdG8gY3V0IHRoZSBwYXN0cmllcy4gRWFjaCBjdXQgdGhhdCBKb2V5IG1ha2VzIGNvcnJlc3BvbmRzIHRvIGEgaG9yaXpvbnRhbCAoeSA9IGMpIG9yIHZlcnRpY2FsICh4ID0gYykgbGluZSBpbiB0aGUgY29vcmRpbmF0ZSBzeXN0ZW0uIEhlbHAgdGhlIGJha2VyIGFzc2VzcyB0aGUgZGFtYWdlIGNhdXNlZCBieSBKb2V5JiMzOTtzIHBhc3RyeSBjdXR0aW5nLiBZb3VyIHRhc2sgaXMgdG8gZGV0ZXJtaW5lLCBmb3IgZWFjaCBKb2V5JiMzOTtzIGN1dCwgaG93IG1hbnkgcGFzdHJpZXMgYXJlIGFmZmVjdGVkIChzdWNoIHRoYXQgYm90aCB0aGUgbGVmdCBhbmQgcmlnaHQgcGFydHMgb2YgdGhlIGN1dCBwYXN0cnkgaGF2ZSBhcmVhcyBncmVhdGVyIHRoYW4gemVybykuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIGJ1cmVrIHBhc3RyaWVzLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBzaXggbm9ubmVnYXRpdmUgaW50ZWdlcnMgc21hbGxlciB0aGFuIDEwPHN1cD42PFwvc3VwPi4gVGhlc2UgbnVtYmVycyBhcmUsIGluIG9yZGVyLCB0aGUgY29vcmRpbmF0ZXMgKHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiksICh4PHN1Yj4yPFwvc3ViPiwgeTxzdWI+MjxcL3N1Yj4pLCAoeDxzdWI+MzxcL3N1Yj4sIHk8c3ViPjM8XC9zdWI+KSBvZiB0aGUgdGhyZWUgcGFzdHJ5LXRyaWFuZ2xlIHZlcnRpY2VzLiBUaGUgdGhyZWUgdmVydGljZXMgd2lsbCBub3QgYWxsIGJlIG9uIHRoZSBzYW1lIGxpbmUuIFRoZSBwYXN0cmllcyBjYW4gdG91Y2ggYXMgd2VsbCBhcyBvdmVybGFwLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGxpbmUgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTSAoMiAmbGU7IE0gJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiBjdXRzLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyBhIHNpbmdsZSBjdXQgbGluZSBlcXVhdGlvbjogJmxkcXVvO3ggPSBjJnJkcXVvOyBvciAmbGRxdW87eSA9IGMmcmRxdW87IChub3RlIHRoZSBzcGFjZXMgYXJvdW5kIHRoZSBlcXVhbHMgc2lnbiksIHdoZXJlIGMgaXMgYSBub25uZWdhdGl2ZSBpbnRlZ2VyIHNtYWxsZXIgdGhhbiAxMDxzdXA+NjxcL3N1cD4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY3V0LCBvdXRwdXQgYSBsaW5lIGNvbnRhaW5pbmcgdGhlIHJlcXVpcmVkIG51bWJlciBvZiBjdXQgcGFzdHJpZXMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==