Ирина работает в экскурсионной компании Саратова. Сегодня она собирается организовать экскурсии по городам Саратов и Энгельс.

Всего существует $$$n_1$$$ достопримечательность в Саратове и $$$n_2$$$ достопримечательность в Энгельсе. Города разделены рекой, но есть $$$m$$$ автобусных маршрутов, которые проходят по мостам и позволяют туристам добраться из Саратова в Энгельс и обратно. Маршрут $$$i$$$-го автобуса проходит от $$$x_i$$$-й достопримечательности в Саратове до $$$y_i$$$-й достопримечательности в Энгельсе, а также в обратном направлении.

Ирина хочет спланировать экскурсии на текущий день. Экскурсионные поездки начинаются в Саратове утром, продолжаются в Энгельсе днем и заканчиваются в Саратове вечером.

Каждый турист начинает свой экскурсионный день с какой-нибудь достопримечательности Саратова, $$$k_i$$$ туристов начинают с $$$i$$$-й достопримечательности. Затем гиды везут их в Энгельс: на каждой достопримечательности Саратова гид выбирает автобусный маршрут, ведущий от этой достопримечательности в Энгельс, и все туристы, отправляющиеся с этой достопримечательности, отправляются в Энгельс по этому автобусному маршруту. После завершения экскурсий в Энгельсе происходит то же самое: для каждой достопримечательности в Энгельсе гид выбирает автобусный маршрут, ведущий от этой достопримечательности в Саратов, и все туристы с этой достопримечательности отправляются в Саратов по этому автобусному маршруту.

Этот процесс может привести к такой ситуации, что некоторые туристы вернутся к той же достопримечательности в Саратове, с которой они начали утром. Очевидно, туристам это не нравится, поэтому Ирина хочет выбрать, куда гиды повезут туристов (как по дороге из Саратова в Энгельс, так и по дороге из Энгельса в Саратов), чтобы минимально возможное количество туристов вернулось к той же достопримечательности, с которой они начали. Помогите Ирине найти оптимальный план!