# Homework 6 Hint of Dragon Curve

## Table of Content
[toc]

---

## Description:
Frieren wants to become a Dragon Warrior, like Po

As she determines to become one, she needs to learn the "Dragon Curve" kung fu style

---

**What is Dragon Curve?**

This is a Dragon Curve (Wikipedia)
https://upload.wikimedia.org/wikipedia/commons/a/a9/Dragon_Curve_unfolding_rectangular_numbered.gif <= [Open to see the GIF]

Initially, there is only 1 stick

The next pattern is copying the previous pattern and rotating by 90 degree

As the pattern can go infinte, we can calculate what the patterns will be in a certain position

---

**Question :**

Let every stick length be 3x1, black boxes, and based on the dragon curve pattern, let :

Index 1 is the first stick of the pattern,
Index 2 is the second stick of the pattern,
Index 3 is the third stick of the pattern,
and so on ... until infinity


Given the pattern length is n and the pattern start at index s,

You need to draw the dragon curve start from index s until index s + n - 1, as the length of the pattern is n in the 2d array

The '#' indicates the pattern (Black), while the blank is '.' represents the blank (White)

**The drawing must fit perfectly in the array**, which means:

The given pattern must fully be shown in the array
The most left/right column and most up/down row can't be a blank row/column

Sample IO Explanation :


**Note : If the gray box is inside the array, leave it as white '.'**

---

## Hint

You can imagine every stick has their own direction from the starting point. For example:
* index 1 is going up,
* index 2 is going right,
* index 3 is going down, and so on.

And as you can observe, for every pattern with length of 2^k^ as k ≥ 0 is integer, then the next 2^k^ pattern (from 2^k^+1 until 2^k+1^) is basicly the same direction as previous pattern with mirrored index, and rotated by 90 degree. You can see GIF below demonstrating how do you know the pattern start from index 1, starting from red point


Since the starting index start could be any number in range 10^18^, there is no way we use bottom-up approach, as it's very slow to calculate 1 by 1, then we are using top-down approach.


To make the array of the board:
* First you need to calculate the size of the array. Let say you finaly made the array size of n with the direction,
* Then from the first index to last index of the array full of blank, you can calculate the up/down/left/right bound.
* The rows of the array will be difference between up until down, while
* The cols of the array will be difference between left until right.
* you can start drawing the pattern from the center (**Center is based on up, down, left, right. NOT THE MEDIAN OF THE ARRAY**) and follow the direction you have calculate