% !TEX program = lualatex % (can also use "xelatex") 
\documentclass[12pt]{article}
\input{ejoi_structure.tex}

\usepackage[bulgarian]{babel}

\begin{document}

\renewcommand{\round}{Ден 2}
\renewcommand{\problemName}{Задача НОД 2}
\renewcommand{\lang}{Български}

\renewcommand{\tl}{$4.5$ sec.}
\renewcommand{\ml}{$512$ MB}
\problem{\problemName}

\begin{center} 
    Кой не обича машинен код? \emoji{slightly-smiling-face}
\end{center}

Даден е масив $a_1, a_2, \dots, a_N$, първоначално пълен със стойности $0$. Дадени са и $Q$ заявки от два типа:
\begin{enumerate}
	\item Добави $x$ към $a_l, a_{l+1}, \dots, a_r$.
	\item Изведи $\sum\limits_{i=l}^{r} a_i$.
\end{enumerate}
Напишете програма, която отговаря на заявките.

\subsection{Детайли по имплементацията}
Програмата, която ще напишете, трябва да е написана на псевдомашинен код в текстов файл (\texttt{txt}). Вашият код може да използва посочените по-долу регистри, както и помощен масив $m_0, m_1, \dots, m_{10^6 - 1}$. Масивът и регистрите пазят 64-битови цели числа.

Нека означим $|R|$ като стойността на регистър $R$. Езикът поддържа следните инструкции:
\begin{lstlisting}
 IN R
\end{lstlisting}
Тази инструкция въвежда число в регистър $R$.
\begin{lstlisting}
 OUT R
\end{lstlisting}
Тази инструкция извежда числото в регистър $R$.
\begin{lstlisting}
 MOV R1 R2
\end{lstlisting}
Тази инструкция копира $|R2|$ в регистър $R1$.
\begin{lstlisting}
 MOV R1 x
\end{lstlisting}
Тази инструкция, използвана по този начин, запазва числото x в регистър $R1$.
\begin{lstlisting}
 ADD R1 R2
\end{lstlisting}
Тази инструкция добавя $|R2|$ към $|R1|$ и резултатът остава в $R1$.
\begin{lstlisting}
 SUB R1 R2
\end{lstlisting}
Тази инструкция изважда $|R2|$ от $|R1|$ и резултатът остава в $R1$.
\begin{lstlisting}
 DIV R1 R2
\end{lstlisting}
Тази инструкция целочислено дели $|R1|$ на $|R2|$ и резултатът остава в $R1$.
\begin{lstlisting}
 MUL R1 R2
\end{lstlisting}
Тази инструкция умножава $|R1|$ по $|R2|$ и резултатът остава в $R1$.
\begin{lstlisting}
 CMP R1 R2
\end{lstlisting}
Тази инструкция сравнява $|R1|$ и $|R2|$ и запазва резултата в регистър $RES$. Резултатът е $0$, ако $|R1| > |R2|$ и $1$, ако $|R1| \leq |R2|$.
\begin{lstlisting}
 LOAD R1 R2
\end{lstlisting}
Тази инструкция зарежда $m_{|R1|}$ в регистър $R2$.
\begin{lstlisting}
 STORE R1 R2
\end{lstlisting}
Тази инструкция запазва $|R2|$ в $m_{|R1|}$.
\begin{lstlisting}
 JZ N
\end{lstlisting}
Тази инструкция казва на интерпретатора да отиде на ред $N$ във Вашия код, единствено ако $|RES| = 0$.
\begin{lstlisting}
 JNZ N
\end{lstlisting}
Тази инструкция казва на интерпретатора да отиде на ред $N$ във Вашия код, единствено ако $|RES| \neq 0$.
\begin{lstlisting}
 RETURN
\end{lstlisting}
Тази инструкция прекратява изпълнението на програмата.
\begin{lstlisting}
 ; comment
\end{lstlisting}
\begin{lstlisting}
 MOV A B ; comment
\end{lstlisting}
Можете да използвате коментари в кода си, използвайки точка и запетая.

\begin{itemize}
	\item $R, R1, R2$: регистър. Може да бъде $A, B, C, D, E, F, G, H$ или $RES$. Имате право да пишете във всички от тях.
	\item $N$: номер на ред в кода. Индексацията започва от $1$.
\end{itemize}

\newpage

\subsection{Вход}
На първия ред от входа се въвеждат $N$ и $Q$. На всеки от следващите $Q$ реда се въвеждат $t, l, r$, където $t$ е типът на заявка. Ако $t=1$, на края на реда се въвежда и числото $x$.

\subsection{Изход}
За всяка заявка от тип $2$ се извежда отговорът.

\subsection{Ограничения}
\begin{itemize}
	\item $1 \leq N, Q \leq 3.10^4$
	\item $1 \leq l \leq r \leq N$
	\item $1 \leq x \leq 10^9$
	\item $1 \leq t \leq 2$
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
\hline
\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & \textbf{Допълнителни ограничения}\\
\hline
$1$ & $10$ & $-$ & $N=1, Q \leq 500$ \\
\hline
$2$ & $35$ & $1$ & $N, Q \leq 500$ \\
\hline
$3$ & $60$ & $1$ & За заявки от тип 1, $l=r$. \\
\hline
$4$ & $45$ & $1-3$ & $-$ \\
\hline
\end{tblr}
\end{table}
\FloatBarrier

\subsection{Примерна програма}
Нека разгледаме примерна програма на този език, която въвежда две числа и извежда сумата им:
\begin{lstlisting}
 IN A
 IN B
 ADD A B
 OUT A
\end{lstlisting}
Да разгледаме друга примерна програма, която въвежда две числа и извежда по-голямото от тях:
\begin{lstlisting}
 IN A
 IN B
 CMP A B
 JZ 6
 JNZ 8
 OUT A
 RETURN
 OUT B
 RETURN
\end{lstlisting}

\subsection{Примерен грейдър}
Предоставеният грейдър чете кода от файл \texttt{nod2.txt} и го изпълнява.

\end{document}

