عدالت شکلاتی


  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

یک کیک مکعب مستطیلی a×b×ca \times b \times c موازی محورهای مختصات داریم. در واقع این کیک تمام نقاط (x,y,z)(x, y, z) است که 0xa0 \leq x \leq a، 0yb0 \leq y \leq b و 0zc0 \leq z \leq c باشد.

داخل این کیک nn قطعه شکلات قرار دارد. هر قطعه شکلات یک مکعب مستطیل موازی محورها است. می‌دانیم که هیچ دو قطعه شکلاتی با هم اشتراک ندارند. هر قطعه شکلات را با شش عدد x1,y1,z1,x2,y2,z2x_1, y_1, z_1, x_2, y_2, z_2\,\,\, نشان می‌دهیم و یعنی تمام نقاط (x,y,z)(x, y, z) که x1xx2x_1 \leq x \leq x_2، y1yy2y_1 \leq y \leq y_2 و z1zz2z_1 \leq z \leq z_2 از کیک شکلاتی هستند. بقیه فضای کیک را خمیر تشکیل داده است.

توضیح تصویر

خانم کاپ‌کیک می‌خواهد این کیک را بین mm نفر تقسیم کند. او می‌خواهد کیک را m1m - 1 برش از بالا (موازی صفحه‌ی yzyz) بزند به طوری که mm قطعه بدست آمده حجم یکسانی شکلات داشته باشند.

از شما می‌خواهیم مختصات این برش‌ها را پیدا کنید.

ورودی🔗

در سطر اول ورودی دو عدد صحیح nn و mm آمده که به ترتیب تعداد قطعات شکلات و تعداد نفرات را نشان می‌دهد.

1n100001 \leq n \leq 10\,000 2m100002 \leq m \leq 10\,000

در سطر دوم ورودی سه عدد صحیح aa، bb و cc آمده که ابعاد کیک را نشان می‌دهد. 1a,b,c1001 \leq a, b, c \leq 100

در nn سطر بعدی، در هر سطر شش عدد صحیح x1,y1,z1,x2,y2,z2x_1, y_1, z_1, x_2, y_2, z_2\,\,\, داده می‌شود که مختصات قطعه شکلاتی را نشان می‌دهد.

0x1<x2a,0y1<y2b,0z1<z2c0 \leq x_1 \lt x_2 \leq a, \quad 0 \leq y_1 \lt y_2 \leq b, \quad 0 \leq z_1 \lt z_2 \leq c

تضمین می‌شود که هیچ دو قطعه شکلاتی با هم اشتراک ندارند.

خروجی🔗

خروجی m1m - 1 خط دارد و در خط iiام عدد اعشاری XiX_i که نشان دهنده‌ی برشی است که باید بزنیم. شما باید برش‌ها را به ترتیب چاپ کنید یعنی:

0<X1<X2<<Xm1<a0 \lt X_1 \lt X_2 \lt \dots \lt X_{m-1} \lt a

زمانی پاسخ شما پذیرفته می‌شود که اختلاف حجم شکلاتی که به هر کس می‌رسد با مقدار دقیق آن حداکثر ۰.۰۰۱ باشد.

مثال🔗

ورودی نمونه ۱🔗

2 3
3 4 5
0 0 0 1 1 1
2 2 2 3 4 5
Plain text

خروجی نمونه ۱🔗

2.222222222217
2.611111111103
Plain text