Tutorial 1A
1 Prove application form of mathematical induction
Define \(S := \left\{\, n\in\mathbb{N}: P(n) \,\right\}\), trivial.
2
Given two nonzero integers \(x\) and \(y\). Suppose \(d \in\mathbb{N}\) such that \(d\mid x\) and \(d\mid y\), and \(d\) satisfies the following property \[\forall c\in\mathbb{Z}\smallsetminus\left\{\, 0 \,\right\}.~ c\mid x \land c\mid y \implies c\mid d.\] Show that \(d = \gcd(x,y)\).
Proof. Let \(d' := \gcd(x,y)\). By definition of \(\gcd\), \(d'\mathbb{Z}= \left\{\, ax + by: a,b\in\mathbb{Z} \,\right\}\), so \(d'\mid x\) and \(d'\mid y\). By hypothesis, \(d' \mid d\).
On the other hand, with Bézout’s identity to write \(d' = ax + by\) for some \(a,b\in\mathbb{Z}\). By hypothesis we have \(d\mid x\) and \(d\mid y\) hence \(d\mid d'\), therefore \(d = d'\).
3 Qn 1.56(iii) on page 54 in [R].
- Find \(d = \gcd ( 12327 , 2409)\) .
- Find integers \(s\) and \(t\) with \(d = 12327 s + 2409 t\) .
- Put the fraction \(2409 / 12327\) in lowest terms.
- Papa Euclid
- Extended papa Euclid
- Divide by \(d\).
3.1 Papa Euclid
Euclidean gcd implemented in Haskell,
which gives
λ gcd 12327 2409
33.2 Extended papa Euclid
To extend gcd, we need a function which for any \(a,d\in\mathbb{Z}\), calculates \(\gcd(a,d)\) and \(c_1,c_2\in\mathbb{Z}\) such that \(c_1a + c_2d = \gcd(a,d)\). We already know that \(\gcd(a,d) = \gcd(d,r)\) where \(a = qd + r\) by division algorithm. Suppose (by recursion) we have \(\gcd(d,r) = xd + yr\), then \[\begin{align*}
\gcd(d,r)
&= xd + yr \\
&= xd + y(a - qd) \\
&= ya + (x-qy)d
\end{align*}\] Hence we can implement extended Euclidean algorithm as such
-- returns (gcd a d, c1, c2)
eea :: Integral a => a -> a -> (a, a, a)
eea a 0 = (abs a, signum a, 0)
eea a d = let (q, r) = a `divMod` d
(res, x, y) = eea d r in
(res, y, x - q*y)Which we can compute and verify as
λ eea 12327 2409
(3,299,-1530)
λ 299 * 12327 - 1530 * 2409
33.3 Division by 3
is left as an exercise for the reader.
4 Proposition 1.55 in [R].
Suppose \[x = p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s} \text{ and } y = p_1^{f_1} p_2^{f_2}\cdots p_s^{f_s}\] are prime factorisations of \(x,y \in \mathbb{N}\) respectively. Where \(p_1,\dots,p_s\) are distinct primes and \(e_i, f_j \geq 0\).
\(x\mid y\) if and only if \(e_i \leq f_i\) for \(i = 1,\dots, s\).
Proof. Suppose \(e_i \leq f_i\), divisibility is trivial, for \[x \cdot p_1^{f_1 - e_1}p_2^{f_2 - e_2} \cdots p_s^{f_s - e_s} = y.\]
Can just whack with question 2.
5
Suppose \(m_1,m_2,m_3\) are mutually coprime positive integers. Let \(r\in\mathbb{Z}\) such that \(m_1\mid r\), \(m_2\mid r\), \(m_3\mid r\). Show that \(m_1m_2m_3 \mid r\).
By Bézout’s identity, there exists \(s,t\in\mathbb{Z}\) such that \[s m_1 + t m_2 = 1.\] Then because \(m_1 \mid r\) and \(m_2 \mid r\), \[\begin{align*} s m_1r + t m_2r &= r \\ s m_1m_2 \frac{r}{m_2} + t m_2 m_1 \frac{r}{m_1} &= r \end{align*}\] we have \(m_1m_2 \mid r\). (Exercise done)
We claim that \(\gcd(m_1m_2, m_3) = 1\). Factorise those integers and use Question 4 to observe that prime factors of \(m_1\) and \(m_2\) do not appear in \(m_3\). Apply above argument again to obtain conclusion.
6 Let \(x_1,\dots,x_n\in\mathbb{Z}\), define \(I = \left\{\, a_1x_1+a_2x_2+\dots+a_nx_n: a_1,\dots,a_n\in\mathbb{Z} \,\right\}\).
Base cases. When \(n=1\), it’s trivial that
- \(I_1 = \left\{\, a_1x_1 : a_1\in\mathbb{Z} \,\right\} = x_1\mathbb{Z}\)
- \(x_1\mid x_1\)
- Suppose \(c\ne 0\) and \(c\mid x_1\) then \(c\mid x_1\).
Induction. Suppose results hold for \(n-1\), then
\(I_n = \left\{\, y + a_nx_n : y \in I_{n-1}, a_n \in\mathbb{Z} \,\right\}\). From IH, we have \(I_{n-1} = d_{n-1}\mathbb{Z}\) for some poz int \(d_{n-1}\), so \[I_n = \left\{\, ad_{n-1} + a_nx_n : a,a_n \in \mathbb{Z} \,\right\} \] then we have \(I_n = d_n\mathbb{Z}\) where \(d_n = \gcd(d_{n-1}, x_n)\).
By IH \(d_{n-1} \mid x_1,\dots,x_{n-1}\), because \(d_n \mid d_{n-1}\), \(d_n\) also divides those guys. Additionally it’s clear by gcd that \(d_n \mid x_n\).
Suppose \(c\ne 0\) and \(c\mid x_i\) for \(i\in\left\{\, 1,\dots,n \,\right\}\), we have by induction hypothesis \(c\mid d_{n-1}\) We also have \(c \mid x_n\), then by question 2, because \(d_n := \gcd(d_{n-1},x_n)\) we have \(c\mid d_n\).
7 ED \(\implies\) PID
Let \((R,+,\cdot)\) be an Integral domain (no zero divisors), and let there be a division algorithm on it.
Proof. Let \(I\) be any ideal, take the image \(N(I\smallsetminus\left\{\, 0 \,\right\}) \subseteq \mathbb{N}\). By well-ordering principle, we have an element \(a\in I\) such that \(N(a)\) is least in the image. We claim that \(I = aR\).
\(aR \subseteq I\) is trivial, for \(a\in I\). Suppose for a contradiction, \(I \supset aR\), then let \(x\in I\) such that \(x\notin aR\), then divide \(x\) by \(a\), we have \[x = aq + r \text{ for some } q,r\in R\text{ with } N(r) \ne 0, N(r) < N(a)\] then we have \(r = x + (-q)a \in I\) with \(N(r) < N(a)\) which raises a contradiction.
8 \(p\)-adic memes.
Note. This guy is not a vector space, for let \(v\in \mathbb{Z}[\frac1p]_{>0}\), \[(\underbrace{1+1+\dots+1}_{p\text{ times}})v = 0v \ne pv\]
Spanning. Let \(x\in \mathbb{Z}[\frac1p]_{>0}\), goal is to show that it can be expressed as a \(\mathbb{Z}/p\mathbb{Z}\) linear combination of vectors in \(\left\{\, p^i : i\in\mathbb{Z} \,\right\}\). From definition, we have \(x = z_0 + z_2\frac1p + \dots + z_m \frac1{p^m}\) for some \(z_i\in\mathbb{Z}\), then simplify the expression as \[ x = \frac{q}{p^m} \text{ for some }q\in\mathbb{Z}. \] Because \(x>0\) and \(p>0\), it’s necessary that \(q>0\), then we can iteratively divide \(q\) by \(p\), like such \[\begin{align*} q &= q_1p + r_1 \\ q_1 &= q_2p + r_2 \\ &\dots \\ q_{k-1} &= q_kp + r_k \\ q_k &= 0 \end{align*}\] Where each \(r_i \in \mathbb{Z}/p\mathbb{Z}\), the last line is the assertion that iteratively dividing by a positive integer by another fixed positive integer eventually gives \(0\), which is easy to see. Then we can rewrite \(q\) as \[q = \underbrace{q_kp^k}_0 + r_kp^{k-1} + \dots + r_2p + r_1.\] Substitute expression into \(x = \frac{q}{p^m}\) gives result.
Linear Independence. Let \(I \subseteq \mathbb{Z}, \left\lvert I \right\rvert<\infty\), \((c_i)_{i\in I} \subseteq \mathbb{Z}/p\mathbb{Z}\) such that \[\sum_{i\in I} c_ip^i = 0.\] Equivalently, let \(r = \min I, t = \max I\), \[ c_rp^r + c_{r+1}p^{r+1} + \dots + c_tp^t = 0 \] Without loss of generality, we can assume that \(r \geq 0\), for we could multiply \(p^{-r}\) into equation otherwise.
Handwave. By uniqueness of remainder, use iterated division by \(p\) to show that all the \(c_i\) are \(0\).
\(p\)-adic norm
\(\left\lVert px \right\rVert = \frac1p \left\lVert x \right\rVert\). Expand.
\(\left\lVert xy \right\rVert = \left\lVert x \right\rVert\left\lVert y \right\rVert\) Expand.
\(\left\lVert x+y \right\rVert \leq \max\{ \left\lVert x \right\rVert, \left\lVert y \right\rVert\}\) Expand.
Metric stuff
I’m lazy…
Tutorial 1B
9 LCM
From tutorial 1A we have \[\gcd(x,y) = p_1^{m_1} p_2^{m_2}\cdots p_s^{m_s}\] where each \(m_i = \min(e_i, f_i)\).
Then \[\operatorname{lcm}(x,y) = p_1^{e_1+f_1-m_1}p_2^{e_2+f_2-m_2}\cdots p_s^{e_s+f_s-m_s} \] and since \(\max(a,b) = a + b - \min(a,b)\), we’re done.
10 More LCM
Let \(d = \gcd(x,y)\), recall the definition \(l = \operatorname{lcm}(x,y) := xy/d\). Since \(d\mid x\), \(y/d \in \mathbb{Z}\), therefore \(x\mid l\). Symmetric argument shows \(y\mid l\).
Factorise the damn thing and argue via prime factors, it becomes uncomfortably obvious.
11 Computation.
11.1 Solve \(3x \equiv 1 \pmod{8}\).
By computer,
λ eea 3 8
(1,3,-1)so a solution is \(x=3\).
11.2 Simultaneous congruence.
Solve \(x\equiv 2\pmod{5}\) and \(3x\equiv 1\pmod{8}\).
First rewrite the second equation as \(x\equiv 3\pmod{8}\) (multiply by inverse of \(3\)).
Chinese Remainder Theorem says that the solution is \(b'sm + btm'\) where \(\gcd(m,m') = sm + tm'\). By computer again,
λ eea 5 8
(1,-3,2)\(s = -3\) and \(t = 2\), so a solution is \(-13 \equiv 27 \pmod{40}\). By Chinese Remainder Theorem all other solutions are of the form \(27 + 40n\) where \(n\in\mathbb{Z}\).
12 Let \(a,b,m\in\mathbb{Z}\) with \(a>0, m>0\) and let \(d=\gcd(a,m)\).
- Show that \(ax \equiv b\pmod{m}\) has an integral solution \(x\) if and only if \(d\mid b\).
First write \(d = as + mt\) for \(s,t\in\mathbb{Z}\).
Suppose \(d\mid b\), let \(k = \frac{b}{d} \in\mathbb{Z}\), then \(b = aks + tkm \equiv a(ks) \pmod{m}\).
Conversely suppose \(ax\equiv b \pmod{m}\) for some \(x\in\mathbb{Z}\). Then \[ax + km = b \text{ for some } m\in\mathbb{Z}.\] Since \(d\mid a\) and \(d\mid m\) we have \(d\mid b\).
- If \(x\) and \(x'\) are both solutions to (i), show that \[x \equiv x' \pmod{\frac{m}{d}}.\]
We have \(ax \equiv ax' \equiv b \pmod{m}\). Let \(k,k'\in\mathbb{Z}\), with \(k\ne k'\) (otherwise trivial) such that \[ax + km = ax' + k'm = b.\] Rearrangement yields \[a(x-x') = (k'-k)m\] By question 2, \(a(x-x') \mid \operatorname{lcm}(a,m) := \frac{am}{d}\). Let \(k''\in\mathbb{Z}\) such that \[a (x-x') \cdot k'' = \frac{am}{d}.\] Cancel \(a\) for \(a\ne 0\) and we have \(x\equiv x'\pmod{\frac{m}{d}}\).
13 Chinese remainder theorem on more equations.
Let \(m_1,m_2,m_3\) be mutually coprime positive integers. Let \(b_1,b_2,b_3 \in\mathbb{Z}\).
- Show that \[\begin{align*} x &\equiv b_1 \pmod{m_1} \\ x &\equiv b_2 \pmod{m_2} \\ x &\equiv b_3 \pmod{m_3} \end{align*}\] has a solution \(x\in\mathbb{Z}\).
By Chinese Remainder Theorem, the first two equations gives us a solution class \[ x \equiv s_1 \pmod{m_1m_2} \] for some \(s_1\in\mathbb{Z}\). By an argument used in tutorial 1A somewhere, \(\gcd(m_1m_2, m_3) = 1\) still, so by Chinese remainder theorem, the congruence equations \[\begin{align*} x &\equiv s_1 \pmod{m_1m_2} \\ x &\equiv b_3 \pmod{m_3} \end{align*}\] has a solution, which is unique modulo \(m_1m_2m_3\). Uniqueness comes from the 1A question.
14 I’m damn stupid
Suppose \[\begin{align*} x \equiv b_1 \pmod{m_1} \\ x \equiv b_2 \pmod{m_2} \end{align*}\] has common solution \(x\in\mathbb{Z}\), then \[\begin{align*} x + k_1m_1 &= b_1 \\ x + k_2m_2 &= b_2 \end{align*}\] rearrangement yields \[ b_1 - b_2 = k_1m_1 - k_2m_2 \] which shows that \(\gcd(m_1,m_2) \mid b_1 - b_2\).
Conversely suppose \(\gcd(m_1,m_2) \mid b_1 - b_2\), then without loss of generality (scaling factor), exists \(k_1, k_2\in\mathbb{Z}\) such that \[\begin{align*} k_1m_1 - k_2m_2 &= b_2 - b_1 \\ x := k_1m_1 + b_1 &= k_2m_2 + b_2 \end{align*}\] verify that \(x\) satisfies the equations.
- If \(x, x'\) are solutions to (i), show that \[x\equiv x' \pmod{\operatorname{lcm}(m_1, m_2)}.\]
Let \[\begin{align*} x &= b_1 + k_1m_1 = b_2 + k_2m_2 \\ x' &= b_1 + k_1'm_1 = b_2 + k_2'm_2 \end{align*}\] then \[\begin{align*} x - x' = (k_1 - k_1')m_1 = (k_2 - k_2') m_2 \end{align*}\] Since \(m_1 \mid x - x'\) and \(m_2 \mid x - x'\) we have \(\operatorname{lcm}(m_1, m_2) \mid x - x'\) giving the conclusion.
15 Gaussian Integers are Euclidean
Draw
16 Gaussian Integers
- \(\pi \in \mathbb{Z}[i]\) is prime if for any \(a,b\in\mathbb{Z}[i]\), \(\pi \mid ab \implies \pi \mid a \lor \pi \mid b\).
- \(\iota \in \mathbb{Z}[i]\) is irreducible if \(\iota\) is not a unit (\(N(\iota) \ne 1\)) and \(\iota = xy \implies N(x) = 1 \lor N(y) = 1\).
16.1 Prime \(\iff\) irreducible
We define \(\gcd\) to be in the first quadrant, with argument in \([0,\pi/2)\). Define \(U := \left\{\, 1,i,-1,-i \,\right\}\) be units of \(\mathbb{Z}[i]\).
Let \(p\in\mathbb{Z}[i]\) be prime. Suppose \(p = ab \implies p \mid ab \implies p\mid a \lor p\mid b\). Case \(p\mid a\), \[1 = \frac{a}{p}b \implies b \in U.\] Symmetric argument for \(p\mid b\).
Let \(p\in\mathbb{Z}[i]\) be irreducible, \[p=ab \implies a \in U \lor b \in U\] Suppose \(p\mid xy\), goal: \(p\mid x\) or \(p\mid y\). Let \(d = \gcd(p,x)\), clearly \(d\mid p\). \[p = dp_1 \text{ for some }p_1\in\mathbb{Z}[i]\] Because \(p\) irreducible, \(d \in pU\) or \(d \in U\).
- Case \(d = pi^{0,1,2,3}\), \(d\mid x\implies p\mid x\).
- Case \(d = 1 = ap + bx\) for some \(a,b\in\mathbb{Z}[i]\), then \[p \mid y = apy + b(xy)\]
17 \(\mathbb{Z}[i]\) is factorial.
Existence of prime factorisation flows exactly like proof in https://blog.nus.edu.sg/2018ma2202s/2018/07/03/1-3-unique-factorization-domain-part-1/ .
⣿⣿⣿⣿⣿⣿⡷⣯⢿⣿⣷⣻⢯⣿⡽⣻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⠸⣿⣿⣆⠹⣿⣿⢾⣟⣯⣿⣿⣿⣿⣿⣿⣽⣻⣿⣿⣿⣿⣿⣿⣿⣿⣷⡌
⣿⣿⣿⣿⣿⣿⣻⣽⡿⣿⣎⠙⣿⣞⣷⡌⢻⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⡄⠹⣿⣿⡆⠻⣿⣟⣯⡿⣽⡿⣿⣿⣿⣿⣽⡷⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣟⣷⣿⣿⣿⡀⠹⣟⣾⣟⣆⠹⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢠⡘⣿⣿⡄⠉⢿⣿⣽⡷⣿⣻⣿⣿⣿⣿⡝⣷⣯⢿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣯⢿⣾⢿⣿⡄⢄⠘⢿⣞⡿⣧⡈⢷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢸⣧⠘⣿⣷⠈⣦⠙⢿⣽⣷⣻⣽⣿⣿⣿⣿⣌⢿⣯⢿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣟⣯⣿⢿⣿⡆⢸⡷⡈⢻⡽⣷⡷⡄⠻⣽⣿⣿⡿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣏⢰⣯⢷⠈⣿⡆⢹⢷⡌⠻⡾⢋⣱⣯⣿⣿⣿⣿⡆⢻⡿⣿⣿⣿⣿⡟⣿
⣿⣿⣿⣿⣿⣿⡎⣿⢾⡿⣿⡆⢸⣽⢻⣄⠹⣷⣟⣿⣄⠹⣟⣿⣿⣟⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⡇⢸⣯⣟⣧⠘⣷⠈⡯⠛⢀⡐⢾⣟⣷⣻⣿⣿⣿⡿⡌⢿⣻⣿⣿⣿⣿⡌
⣿⣿⣿⣿⣿⣿⣧⢸⡿⣟⣿⡇⢸⣯⣟⣮⢧⡈⢿⣞⡿⣦⠘⠏⣹⣿⣽⢿⣿⣿⣿⣿⣯⣿⣿⣿⡇⢸⣿⣿⣾⡆⠹⢀⣠⣾⣟⣷⡈⢿⣞⣯⢿⣿⣿⣿⢷⠘⣯⣿⣿⣿⣿⣷
⣿⣿⣿⣿⣿⣿⣿⡈⣿⢿⣽⡇⠘⠛⠛⠛⠓⠓⠈⠛⠛⠟⠇⢀⢿⣻⣿⣯⢿⣿⣿⣿⣷⢿⣿⣿⠁⣾⣿⣿⣿⣧⡄⠇⣹⣿⣾⣯⣿⡄⠻⣽⣯⢿⣻⣿⣿⡇⢹⣾⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡇⢹⣿⡽⡇⢸⣿⣿⣿⣿⣿⣞⣆⠰⣶⣶⡄⢀⢻⡿⣯⣿⡽⣿⣿⣿⢯⣟⡿⢀⣿⣿⣿⣿⣿⣧⠐⣸⣿⣿⣷⣿⣿⣆⠹⣯⣿⣻⣿⣿⣿⢀⣿⢿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⠘⣯⡿⡇⢸⣿⣿⣿⣿⣿⣿⣿⣧⡈⢿⣳⠘⡄⠻⣿⢾⣽⣟⡿⣿⢯⣿⡇⢸⣿⣿⣿⣿⣿⣿⡀⢾⣿⣿⣿⣿⣿⣿⣆⠹⣾⣷⣻⣿⡿⡇⢸⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⡇⢹⣿⠇⢸⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠻⡇⢹⣆⠹⣟⣾⣽⣻⣟⣿⣽⠁⣾⣿⣿⣿⣿⣿⣿⣇⣿⣿⠿⠛⠛⠉⠙⠋⢀⠁⢘⣯⣿⣿⣧⠘⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⡈⣿⡃⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡙⠌⣿⣆⠘⣿⣞⡿⣞⡿⡞⢠⣿⣿⣿⣿⣿⡿⠛⠉⠁⢀⣀⣠⣤⣤⣶⣶⣶⡆⢻⣽⣞⡿⣷⠈⣿⣻⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⠘⠁⠉⠉⠉⠉⠉⠉⠉⠉⠉⠙⠛⠛⢿⣄⢻⣿⣧⠘⢯⣟⡿⣽⠁⣾⣿⣿⣿⣿⣿⡃⢀⢀⠘⠛⠿⢿⣻⣟⣯⣽⣻⣵⡀⢿⣯⣟⣿⢀⣿⣽⣿⣿
⣿⣿⣿⣟⣿⣿⣿⣿⣶⣶⡆⢀⣿⣾⣿⣾⣷⣿⣶⠿⠚⠉⢀⢀⣤⣿⣷⣿⣿⣷⡈⢿⣻⢃⣼⣿⣿⣿⣿⣻⣿⣿⣿⡶⣦⣤⣄⣀⡀⠉⠛⠛⠷⣯⣳⠈⣾⡽⣾⢀⣿⢾⣿⣿
⣿⢿⣿⣿⣻⣿⣿⣿⣿⣿⡿⠐⣿⣿⣿⣿⠿⠋⠁⢀⢀⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣌⣥⣾⡿⣿⣿⣷⣿⣿⢿⣷⣿⣿⣟⣾⣽⣳⢯⣟⣶⣦⣤⡾⣟⣦⠘⣿⢾⡁⢺⣿⣿⣿
⣿⣻⣿⣿⡷⣿⣿⣿⣿⣿⡗⣦⠸⡿⠋⠁⢀⢀⣠⣴⢿⣿⣽⣻⢽⣾⣟⣷⣿⣟⣿⣿⣿⣳⠿⣵⣧⣼⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣽⣳⣯⣿⣿⣿⣽⢀⢷⣻⠄⠘⣯⣿⣿
⣿⢷⣻⣿⣿⣷⣻⣿⣿⣿⡷⠛⣁⢀⣀⣤⣶⣿⣛⡿⣿⣮⣽⡻⣿⣮⣽⣻⢯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⢀⢸⣿⢀⡆⣿⣿⣿
⠸⣟⣯⣿⣿⣷⢿⣽⣿⣿⣷⣿⣷⣆⠹⣿⣶⣯⠿⣿⣶⣟⣻⢿⣷⣽⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢀⣯⣟⢀⡇⢼⣿⣿
⣇⠹⣟⣾⣻⣿⣿⢾⡽⣿⣿⣿⣿⣿⣆⢹⣶⣿⣻⣷⣯⣟⣿⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢀⡿⡇⢸⡇⢸⣿⡇
⣿⣆⠹⣷⡻⣽⣿⣯⢿⣽⣻⣿⣿⣿⣿⣆⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠛⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⢸⣿⠇⣼⡇⢸⡿⢠
⡙⠾⣆⠹⣿⣦⠛⣿⢯⣷⢿⡽⣿⣿⣿⣿⣆⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠎⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⢀⣿⣾⣣⡿⡇⢸⢃⣾
⣿⣷⡌⢦⠙⣿⣿⣌⠻⣽⢯⣿⣽⣻⣿⣿⣿⣧⠩⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⢰⢣⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⢀⢀⢿⣞⣷⢿⡇⠉⣼⣿
⣿⣽⣆⠹⣧⠘⣿⣿⡷⣌⠙⢷⣯⡷⣟⣿⣿⣿⣷⡀⡹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣈⠃⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢀⣴⡧⢀⠸⣿⡽⣿⢀⣾⣿⣿
⢻⣽⣿⡄⢻⣷⡈⢿⣿⣿⢧⢀⠙⢿⣻⡾⣽⣻⣿⣿⣄⠌⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠛⢁⣰⣾⣟⡿⢀⡄⢿⣟⣿⢀⣿⣿⣿
⡄⢿⣿⣷⢀⠹⣟⣆⠻⣿⣿⣆⢀⣀⠉⠻⣿⡽⣯⣿⣿⣷⣈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⢀⣠⠘⣯⣷⣿⡟⢀⢆⠸⣿⡟⢸⣿⣿⣿
⣷⡈⢿⣿⣇⢱⡘⢿⣷⣬⣙⠿⣧⠘⣆⢀⠈⠻⣷⣟⣾⢿⣿⣆⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⣠⡞⢡⣿⢀⣿⣿⣿⠇⡄⢸⡄⢻⡇⣼⣿⣿⣿
⣿⣷⡈⢿⣿⡆⢣⡀⠙⢾⣟⣿⣿⣷⡈⠂⠘⣦⡈⠿⣯⣿⢾⣿⣆⠙⠻⠿⠿⠿⠿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⢋⣠⣾⡟⢠⣿⣿⢀⣿⣿⡟⢠⣿⢈⣧⠘⢠⣿⣿⣿⣿
⣿⣿⣿⣄⠻⣿⡄⢳⡄⢆⡙⠾⣽⣿⣿⣆⡀⢹⡷⣄⠙⢿⣿⡾⣿⣆⢀⡀⢀⢀⢀⢀⢀⢀⢀⢀⢀⢀⢀⢀⣀⣠⣴⡿⣯⠏⣠⣿⣿⡏⢸⣿⡿⢁⣿⣿⢀⣿⠆⢸⣿⣿⣿⣿
⣿⣿⣿⣿⣦⡙⣿⣆⢻⡌⢿⣶⢤⣉⣙⣿⣷⡀⠙⠽⠷⠄⠹⣿⣟⣿⣆⢙⣋⣤⣤⣤⣄⣀⢀⢀⢀⢀⣾⣿⣟⡷⣯⡿⢃⣼⣿⣿⣿⠇⣼⡟⣡⣿⣿⣿⢀⡿⢠⠈⣿⣿⣿⡟
⣿⣿⣿⣿⣿⣷⣮⣿⣿⣿⡌⠁⢤⣤⣤⣤⣬⣭⣴⣶⣶⣶⣆⠈⢻⣿⣿⣆⢻⣿⣿⣿⣿⣿⣿⣷⣶⣤⣌⣉⡘⠛⠻⠶⣿⣿⣿⣿⡟⣰⣫⣴⣿⣿⣿⣿⠄⣷⣿⠆⢻⣿⣿⡇
- ine