تنتشر $N$ من الماعز في سهل واسع وترعى بهدوء. لا توجد اثنتان في الموضع نفسه. هذه الماعز كسولة؛ لا تنتقل من مكانها بل تدور فيه أحيانًا فقط. وفي الحقيقة كلها روبوتات لا تستطيع المشي بل الدوران في مكانها فقط. أنوفها مصابيح LED يمكن إضاءتها عن بُعد، وعيونها كاميرات عالية الأداء يمكن مشاهدة صورها عن بُعد في الوقت الحقيقي وحفظ المشاهد المطلوبة. تستطيع كل واحدة رؤية أنفها، ولعيونها خاصية الرؤية عبر الأجسام، فتستطيع معرفة عدد الماعز حتى عندما تتراكب في الصورة. مجال الرؤية الأفقي هو $180^\circ$، ويشمل حدود هذا المجال أيضًا.

بحسب مواضع الماعز، قد تتمكن بعض الماعز من رؤية الماعز $N$ كلها في آن واحد، بينما قد لا تتمكن أخرى مهما كان اتجاه نظرها. مثلًا، في الشكل التالي للماعز الست المرقمة من $0$ إلى $5$، تستطيع الماعز رقم $5$ رؤية الست كلها معًا، بينما لا تستطيع رقم $2$ ذلك في أي اتجاه.

لإجراء تجربة خاصة، نختار اثنتين مختلفتين من الماعز تستطيع كل منهما رؤية الماعز $N$ كلها معًا، ثم نختار واحدة عشوائية من البقية. نضيء أنوف الثلاث المختارة لتُعرف مواضعها من أي مكان. نراقب صور عيونها ونحفظ لكل واحدة مشهدًا تظهر فيه الماعز الثلاث المضيئة معًا في الإطار نفسه. نفحص المشاهد الثلاثة واحدًا واحدًا. في كل مشهد نضع علامة خاصة على الماعز الثلاث المضيئة وعلى جميع الماعز الواقعة بين الاثنتين الأخريين المضيئتين، بما في ذلك الحدود. الهدف هو حساب عدد الماعز من بين $N$ التي تحصل على علامة في المشاهد الثلاثة كلها.

مثلًا، إذا مُثِّلت الثلاث المختارة من بين الست بنقاط حمراء، فالأشكال التالية توضح الماعز التي تحصل على علامة من منظور كل واحدة مختارة. (هذه الأشكال ليست المشاهد المحفوظة نفسها.) في هذه الحالة تحصل $4$ من الماعز على العلامة في المرات الثلاث كلها.

عليك تنفيذ الدالتين التاليتين لهذه التجربة.

• void init( int x[], int y[] ): تُستدعى هذه الدالة أولًا ومرة واحدة فقط. المصفوفتان (المتجهان) x وy حجمهما $N$. يعطي الوسيطان x[0..N-1] وy[0..N-1] إحداثيات $x$ و$y$ للماعز. موضع الماعز رقم $i$ ($0\le i\le N-1$) هو (x[i], y[i]).
• int count( int a, int b, int c ): باستخدام إحداثيات الماعز الثلاث المعطاة (x[a], y[a]) و(x[b], y[b]) و(x[c], y[c])، تحسب وتعيد عدد الماعز التي تُعلَّم في المرات الثلاث كلها.

تفاصيل التنفيذ

يجب تقديم ملف واحد اسمه goat.cpp تُنفَّذ فيه الدوال التالية.

void init( int x[], int y[] );
int count( int a, int b, int c );

يجب أن تعمل هذه الدوال كما وُصف أعلاه. يمكنك تعريف دوال أخرى للاستخدام الداخلي. يجب ألا ينفذ الكود المقدَّم إدخالًا أو إخراجًا أو يصل إلى ملفات أخرى.

مثال على برنامج التقييم

يقرأ برنامج التقييم المرفق المدخلات بالصيغة التالية.

• السطر الأول: $N\ Q$، حيث $N$ عدد الماعز و$Q$ عدد الاستعلامات.
• كل سطر من الأسطر $N$ التالية: $x\ y$، وهما إحداثيا $x$ و$y$ لإحدى الماعز.
• كل سطر من الأسطر $Q$ التالية: $a\ b\ c$ ($a,b,c$)، وهي أرقام الماعز الثلاث، حيث $0\le a,b,c\le N-1$.

لكل استعلام، يطبع برنامج التقييم عدد الماعز التي تحقق الشرط في سطر منفصل.

القيود

• $3\le N\le 3000$
• $1\le Q\le 5\times10^6$
• إحداثيات $x$ و$y$ لجميع الماعز بين $0$ و$10^9$ شاملًا الحدين.

المهام الفرعية

1 (5 نقطة)

• $N\le 500$, $Q\le 10^5$
• لا تقع أي ثلاث نقاط على خط مستقيم واحد.

2 (17 نقطة)

• $N\le 500$, $Q\le 10^5$

3 (10 نقطة)

• $N\le 500$
• لا تقع أي ثلاث نقاط على خط مستقيم واحد.

4 (8 نقطة)

• $N\le 500$

5 (29 نقطة)

• لا تقع أي ثلاث نقاط على خط مستقيم واحد.

6 (31 نقطة)

• لا قيود إضافية.

أمثلة

الإدخال 1

6 3
0 0
1 1
2 2
4 3
0 2
2 0
0 5 2
1 3 4
4 1 5

الإخراج 1

4
4
3

فيما يلي استدعاءات الدوال ونتائجها للمثال 1 بالترتيب.