Sachverhalt:
A.
Am 18. August 2015 kam es zu eine Schlägerei zwischen A._ und X._. A._ stellte am 3. September 2015 Strafantrag gegen X._.
B.
Die Staatsanwaltschaft des Kantons Graubünden erliess am 28. Juni 2016 eine Teileinstellungsverfügung und sandte diese an die Adresse von A._ an der B._-Strasse in C._. Die Post retournierte die Sendung an die Staatsanwaltschaft mit dem Vermerk, dass der Empfänger an der angegebenen Adresse nicht habe ermittelt werden können. Daraufhin sandte die Staatsanwaltschaft am 19. Juli 2016 die Verfügung mit gewöhnlicher A-Post an die neue Adresse von A._ an der D._-Strasse in C._.
C.
A._ stellte am 26. Juli 2016 bei der Staatsanwaltschaft ein Gesuch um Wiederherstellung der Beschwerdefrist gegen die Teileinstellungsverfügung. Die Staatsanwaltschaft überwies dieses zuständigkeitshalber an das Kantonsgericht von Graubünden. Dieses verfügte am 2. September 2016, dass auf das Gesuch nicht eingetreten werde.
Das Kantonsgericht erwägt zusammengefasst, dass wer ein Wiederherstellungsgesuch stellt, die versäumte Verfahrenshandlung innert 30 Tagen nachzuholen habe (<ref-law>). Der Beschwerdeführer habe keine Beschwerde gegen die Verfügung der Staatsanwaltschaft eingereicht, womit er die versäumte Verfahrenshandlung nicht nachgeholt habe. Auf das Wiederherstellungsgesuch sei demnach nicht einzutreten. Ob die Teileinstellungsverfügung überhaupt rechtswirksam zugestellt worden sei, könne offenbleiben.
D.
A._ führt Beschwerde in Strafsachen. Er beantragt, die Verfügung des Kantonsgerichts sei aufzuheben und die Frist zur Einreichung einer Beschwerde gegen die Verfügung der Staatsanwaltschaft sei wiederherzustellen. Ausserdem sei diese an das richtige Zustelldomizil zu senden. A._ ersucht um unentgeltliche Rechtspflege und Verbeiständung.
E.
Die Staatsanwaltschaft und das Kantonsgericht beantragen, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. A._ verzichtete auf weitergehende Bemerkungen.

Erwägungen:
1.
1.1.
Der Beschwerdeführer rügt, dass die Teileinstellungsverfügung nie richtig zugestellt worden sei. Die Beschwerdefrist habe überhaupt nicht zu laufen begonnen; sie könne deshalb auch nicht wiederhergestellt werden. Die Vorinstanz hätte demnach die Frage, ob eine rechtswirksame Zustellung erfolgt sei, nicht offenlassen dürfen. Der Beschwerdeführer macht diesbezüglich geltend, dass er anwaltlich vertreten gewesen sei, weshalb die Zustellung rechtsgültig nur an seinen Rechtsbeistand hätte erfolgen dürfen.
1.2. Ein nicht rechtsgültig zugestellter Entscheid entfaltet keine Rechtswirkung; Fristen werden nicht ausgelöst. Einem Betroffenen kann folglich auch nicht vorgehalten werden, er habe eine Frist verpasst. Eine Wiederherstellung zufolge versäumter Fristen im Sinne von <ref-law> fällt insoweit ausser Betracht (<ref-ruling> E. 2.4). Die in <ref-law> geregelten Bedingungen zur Fristwiederherstellung kommen ebenfalls nur zur Anwendung, wenn der zur Diskussion stehende Entscheid rechtsgültig eröffnet worden ist. Dem Beschwerdeführer ist daher insofern zuzustimmen, als die Vorinstanz nicht davon absehen hätte dürfen, zu bestimmen, ob die Teileinstellungsverfügung der Staatsanwaltschaft korrekt zugestellt worden war.
Der Beschwerdeführer wurde am 3. September 2015 von der Polizei als Beschuldigter befragt; sein amtlicher Verteidiger war an der Einvernahme anwesend (kantonale Akten, act. 3/14). Am selben Tag stellte der Beschwerdeführer einen Strafantrag gegen X._ (kantonale Akten, act. 3/4). Dem entsprechenden Formular, welches nicht Teil des Einvernahmeprotokolls ist, ist nicht zu entnehmen, dass sich der Beschwerdeführer in diesem Zusammenhang anwaltlich vertreten liess. Ausserdem bezieht sich die (amtliche) Verteidigung als solche einzig auf jenes Verfahren, in welchem der Betroffene beschuldigt ist und nicht auf allfällige andere Verfahren (vgl. <ref-law>; Urteil 1B_196/2014 vom 8. Juli 2014 E. 3.2). Dass die Staatsanwaltschaft ihre Verfügung dem Beschwerdeführer persönlich eröffnete, ist somit richtig. Der Beschwerdeführer räumt ein, die zweite, per A-Post erfolgte Sendung der Staatsanwaltschaft erhalten zu haben (Beschwerde, S. 6), womit die Teileinstellungsverfügung ihm gegenüber rechtsgültig eröffnet worden ist (<ref-ruling> E. 4.3; Urteil 6B_390/2013 vom 6. Februar 2014 E. 2.3.2; je mit Hinweisen). Die Rüge ist unbegründet.
2.
Die Beschwerde ist abzuweisen. Die Kosten sind dem unterliegenden Beschwerdeführer aufzuerlegen (<ref-law>). Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist abzuweisen, weil die Beschwerde von vornherein aussichtslos war. Der finanziellen Lage des Beschwerdeführers ist mit herabgesetzten Gerichtskosten Rechnung zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3.
Die Gerichtskosten von Fr. 1'200.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird den Parteien und dem Kantonsgericht von Graubünden, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 15. Juni 2017
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Moses