%!TeX program=lualatex

\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{0.2cm}

\begin{document}

\renewcommand{\tl}{$0.3$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача D13. ДВОЙКИ}
\addauthor{Автор: Борис Михов}{2026}{03}{16}
\renewcommand{\header}{
	XLII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА\\
	Национален кръг, Варна, 13-16 март 2026 г.\\
	Група D, 6 клас
}
	
	Сашка наскоро научи за операцията $+$, като за да я упражни, тя има да реши дълго домашно. То се състои от $1$ задача с $T$ подточки, като във всяка подточка се цели решаване на една и съща задача. В $i$-тата подточка, Сашка разполага с двойката числа $(a_i,b_i)$ и има правото да направи следните две операции:
	
	\begin{itemize}
		\item $(a_i,b_i) \rightarrow (a_i+b_i,b_i)$. Иначе казано, да замени $a_i$ със сбора на $a_i+b_i$.
		\item $(a_i,b_i) \rightarrow (a_i,a_i+b_i)$. Иначе казано, да замени $b_i$ със сбора на $a_i+b_i$.
	\end{itemize}
	
	Във всяка една задача я питат дали е възможно след краен брой операции, $(a_i,b_i)$ да стане равна на $(c_i,d_i)$ и ако е възможно, да се каже минималният брой операции, нужни, за да се постигне това. Забележете, че $(a_i,b_i)=(c_i,d_i)$, тогава и само тогава, когато $a_i=c_i$ и $b_i=d_i$, например $(1,3)\neq(3,1)$. Сашка осъзна, че тази задача ще е по-интересна за решаване чрез компютър. Тъй като тя Ви познава и знае, че вие ще участвате на финалния кръг на Националната олимпиада по информатика, тя ви моли да напишете програма \texttt{\textbf{pairs}}, която да реши домашното й.
	\vspace{-2mm}
	\subsection{Вход}
	На първия ред от стандартния вход е дадено цялото число $T$. На следващите $T$ реда са характеризирани подточките, като на $i$-тия ред са дадени $4$ цели числа, а именно $a_i,b_i,c_i,d_i$.
	\vspace{-2mm}
	\subsection{Изход}
	На стандартния изход oтпечатайте на отделни редове отговорите на всяка една подточка, като $i$-тият ред да съдържа отговора за $i$-тата подточка. Ако не е възможно да се достигне $(c_i,d_i)$, отпечатайте числото $-1$.
	\vspace{-2mm}
	\subsection{Ограничения}
	\vspace{0.1em}
	\begin{itemize}
		\item $1 \leq T \leq 10^5$
		\item $1 \leq a_i,b_i,c_i,d_i \leq 10^{18}$
	\end{itemize}
	\vspace{-2mm}
	\subsection{Оценяване}
	\begin{itemize}
		\item Тестовете, които носят точки, са $10$ на брой.
		\item Нулевият тест ще бъде примерния тест, който няма да носи точки.
		\item В първия тест, $T \leq 10^3$ и ако има решение, отговорът е до $3$;
		\item Във втория тест, $T \leq 10^3$ и $a_i = c_i$;
		\item В третия до петия тест, $T \leq 10^3$ и $a_i, b_i, c_i, d_i \leq 10^5$;
		\item В шестия тест, $a_i = b_i = 1$ за всяко $1 \leq i \leq T$;
		\item В седмия тест, $a_i = b_i$ за всяко $1 \leq i \leq T$;
		\item В осмия до десетия тест, няма допълнителни ограничения.
	\end{itemize}
	\vspace{-2mm}
	%\pagebreak
	\subsection{Пример}
	\begin{table}[ht]
		\begin{tblr}{|X[42,l]|X[8,l]|X[50,l]|}
			\hline
			\textbf{Вход} & \textbf{Изход} & \textbf{Пояснение на примера} \\
			\hline
			\texttt{5\\2 4 2 8\\5 3 5 2\\5 3 8 19\\5 3 5 3\\1 2 2 1} & 
			\texttt{2\\-1\\3\\0\\-1} &
			{\tabitem $(2,4)\rightarrow(2,6)\rightarrow(2,8)$\\\tabitem Не е възможно.\\ \tabitem $(5,3)\rightarrow(8,3)\rightarrow(8,11)\rightarrow(8,19)$\\ \tabitem Не са нужни операции.\\\tabitem Не е възможно.}\\
			\hline
		\end{tblr}
	\end{table}
	
\end{document}
