//--------------------------------------------------------------------------------
//SASAOJ-A_[함수+포인터] swap 함수 만들기
#include <stdio.h>

//
void myswap(int *a, int *b) {
    if(*a<*b) return;
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
//

int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    myswap(&a, &b);
    printf("%d %d", a, b);
}
//--------------------------------------------------------------------------------
//SASAOJ-B_[함수+포인터] 매개변수와 포인터1
#include<stdio.h>

//
void f(int a, int b, int *c, int *d) {
    *c=a+b;
    *d=a-b;
}
//

int main() {
    int a,b,c,d;
    scanf("%d %d",&a,&b);
    f(a,b,&c,&d);
    printf("%d + %d = %d\n",a,b,c);
    printf("%d - %d = %d\n",a,b,d);
    return 0;
}
//--------------------------------------------------------------------------------
//SASAOJ-C_[함수+포인터] 배열과 포인터1
#include <stdio.h>

//
int f(int *arr, int cnt) {
    int res=-100;
    for(int i=0; i<cnt; i++) {
        res=res>arr[i]?res:arr[i];
    }
    return res;
}
//

int main() {
   int a[10];
   for(int i=0;i<10;i++)
      scanf("%d",a+i);
   printf("%d\n",f(a, 10));
   return 0;
}
//--------------------------------------------------------------------------------
//SASAOJ-D_(포인터) 거꾸로 출력하기
#include <stdio.h>
#include <stdlib.h>
int main() {
    int n;
    scanf("%d", &n);

    int *arr=(int *)malloc(sizeof(int)*(n+10));
    for(int i=0; i<n; i++) scanf("%d", arr+i);
    for(int i=n-1; i>=0; i--) printf("%d ", *(arr+i));
}
//--------------------------------------------------------------------------------
//SASAOJ-E_(포인터) 부분 문자열
#include <stdio.h>
#include <stdlib.h>

int main() {
    char *s=(char *)malloc(sizeof(char)*110);
    int a, b;
    scanf("%s", s);
    scanf("%d %d", &a, &b);
    for(int i=a-1; i<b; i++) printf("%c", *(s+i));
}
//--------------------------------------------------------------------------------
//SASAOJ-F_두 점 간의 거리
#include <stdio.h>
#include <math.h>

double dist(int dx, int dy) {
    return sqrt(dx*dx+dy*dy);
}

int main() {
    int x[2], y[2];
    for(int i=0; i<2; i++) scanf("%d %d", &x[i], &y[i]);

    printf("%.2lf", dist(x[0]-x[1], y[0]-y[1]));
}
//--------------------------------------------------------------------------------
//SASAOJ-G_여러 점 간의 거리
#include <stdio.h>
#include <math.h>

double dist(int dx, int dy) {
    return sqrt(dx*dx+dy*dy);
}

int main() {
    int n, x, y;
    double res=0;
    scanf("%d", &n);
    scanf("%d %d", &x, &y);

    for(int i=0; i<n-1; i++) {
        int nx, ny;
        scanf("%d %d", &nx, &ny);
        res+=dist(x-nx, y-ny);
        x=nx, y=ny;
    }
    printf("%.2lf", res);
}
//--------------------------------------------------------------------------------
//SASAOJ-H_광역시
#include <stdio.h>
#include <math.h>
#include <algorithm>

struct City { long long p, dist; };
City A[10010];

bool cmp(City A, City B) {
    if(A.dist!=B.dist) return A.dist<B.dist;
    return A.p>B.p;
}

int main() {
    int n;
    long long p;

    scanf("%d %lld", &n, &p);

    for(int i=0; i<n; i++) {
        int x, y;
        scanf("%d %d %lld", &x, &y, &A[i].p);
        A[i].dist=x*x+y*y;
    }
    std::sort(A, A+n, cmp);

    for(int i=0; i<n; i++) {
        p+=A[i].p;
        if(p>=1000000) {
            printf("%.3lf", sqrt(A[i].dist));
            return 0;
        }
    }
    printf("-1");
}
//--------------------------------------------------------------------------------
//SASAOJ-I_(함수) 키가 더 큰 학생은?
#include<stdio.h>
struct Student {
  int no;
  char name[10];
  int height;
};

//
void swap(Student *A, Student *B) {
    if(A->height>B->height) return;
    Student tmp=*A;
    *A=*B;
    *B=tmp;
}
//

int main() {
  struct Student a,b;
  scanf("%d %s %d",&a.no, a.name, &a.height);
  scanf("%d %s %d",&b.no, b.name, &b.height);
  swap(&a,&b);
  printf("%d %s %d",a.no, a.name, a.height);
}
//--------------------------------------------------------------------------------
//SASAOJ-J_(함수) 2차 방정식을 풀어보자.
#include<stdio.h>
#include<math.h>
struct X { double a,b; };

//
X solve(int a, int b, int c) {
    X A;
    if(a<0) {
        A.a=(-b+sqrt(b*b-4*a*c))/(2*a);
        A.b=(-b-sqrt(b*b-4*a*c))/(2*a);
    }
    else {
        A.a=(-b-sqrt(b*b-4*a*c))/(2*a);
        A.b=(-b+sqrt(b*b-4*a*c))/(2*a);
    }
    return A;
}
//

int main() {
    struct X s;
    int a,b,c;
    scanf("%d %d %d",&a, &b, &c);
    s=solve(a,b,c);
    if(s.a==s.b) printf("%.2lf",s.a);
    else printf("%.2lf %.2lf",s.a, s.b);
}
//--------------------------------------------------------------------------------
//SASAOJ-K_(구조체) 안전한 배열 만들기
#include<stdio.h>

struct Array {
  private:
    int a[5],size=5;
  public:
    void printArray();
    void setValue(int, int);
};

//
void Array::setValue(int idx, int val) {
    if(idx<0||idx>=size) return;
    a[idx]=val;
}
void Array::printArray() {
    for(int i=0; i<size; i++) printf("%d ", a[i]);
}
//

int main() {
  Array a;
  int idx,v;
  for(int i=0;i<10;i++) {
    scanf("%d%d",&idx,&v);
    a.setValue(idx,v);
  }
  a.printArray();
}
//--------------------------------------------------------------------------------
//SASAOJ-L_(구조체) 포함된 문제 세기
#include<stdio.h>
#include<string.h>

struct MyString {
  private:
    char s[100];
  public:
    void setString(char *p);
    int countChar(char c);
};
void MyString::setString(char *p) {
  strcpy(s,p);
}
int MyString::countChar(char c) {
  int cc=0;
  for(int i=0;s[i];i++)
    if(s[i]==c) cc++;
  return cc;
}

//
int main() {
    MyString ms;
    char a, b, c, s[100]={};
    int res=0;

    scanf("%s", s);
    ms.setString(s);
    scanf(" %c %c %c", &a, &b, &c);
    res=ms.countChar(a)+ms.countChar(b)+ms.countChar(c);

    printf("%d", res);
}
//
//--------------------------------------------------------------------------------
//SASAOJ-M_(구조체) 문자열 분류하기
#include<stdio.h>
#include<string.h>

struct MyString {
  private:
    char s[100];
  public:
    void setString(char *p);
    int countCap();  //대문자 count
    int countSmall();  //소문자 count
    int countNum();  // 숫자 count
};

//
void MyString::setString(char *p) {
    strcpy(s, p);
}
int MyString::countCap() {
    int cnt=0;
    for(int i=0; s[i]; i++) {
        if('A'<=s[i]&&s[i]<='Z') cnt++;
    }
    return cnt;
}
int MyString::countSmall() {
    int cnt=0;
    for(int i=0; s[i]; i++) {
        if('a'<=s[i]&&s[i]<='z') cnt++;
    }
    return cnt;
}
int MyString::countNum() {
    int cnt=0;
    for(int i=0; s[i]; i++) {
        if('0'<=s[i]&&s[i]<='9') cnt++;
    }
    return cnt;
}
//

int main() {
  MyString ms;
  char s[100];
  scanf("%s",s);
  ms.setString(s);
  printf("%d %d %d",ms.countNum(),ms.countCap(),ms.countSmall());
}
//--------------------------------------------------------------------------------
//SASAOJ-N (리스트) 카드 나열하기 1
#include<stdio.h>
struct Card { char k; int v; };
class Clist {
  private:
    Card clist[11];
    int size=0;
  public:
    void insertCard(int idx, Card data);
    void printList();
};

//
void Clist::insertCard(int idx, Card data) {
    if(idx<=0||idx>size+1||size>=10) return;
    for(int i=size; i>=idx; i--) {
        clist[i+1]=clist[i];
    }
    clist[idx]=data;
    size++;
}
void Clist::printList() {
    for(int i=1; i<=size; i++) printf("%c%d ", clist[i].k, clist[i].v);
}
//

int main() {
  Card c;
  Clist list;
  int idx;
  for(int i=0;i<10;i++) {
    scanf(" %c %d %d", &c.k, &c.v, &idx);
    list.insertCard(idx, c);
  }
  list.printList();
}
//--------------------------------------------------------------------------------
//SASAOJ-O_(리스트) 정올 참여학생 리스트 만들기 1
#include <stdio.h>
struct Card { int num; char s[15]={}; };
struct MyList {
  private :
    Card My[110];
    int size=0;
  public :
    void insertCard(Card data);
    void deleteCard(int num);
    void printCard(int idx);
};

void MyList::insertCard(Card data) {
    My[0]={0, 0};

    int i;
    for(i=1; i<=size && My[i].num<data.num; i++);

    if(i<=size && My[i].num==data.num) return; // 범위 체크 주의! 안 그러면 쓰레기값과 비교하게 될 수도..
    for(int j=size; j>=i; j--) {
        My[j+1]=My[j];
    }
    My[i]=data;
    size++;
}
void MyList::deleteCard(int num) {
    int i;
    for(i=1; i<=size && My[i].num<num; i++);

    if(i<=size && My[i].num==num) {
        for(int j=i; j<size; j++)
            My[j]=My[j+1];

        size--;
    }
}
void MyList::printCard(int idx) {
    if(idx<=0||idx>size) return;
    printf("%d %s\n", My[idx].num, My[idx].s);
}
int main() {
    int n;
    char c;
    Card D;
    MyList ml;
    scanf("%d", &n);

    for(int i=0; i<n; i++) {
        scanf(" %c %d %s", &c, &D.num, D.s);
        if(c=='I') ml.insertCard(D);
        if(c=='D') ml.deleteCard(D.num);
    }
    for(int i=0; i<5; i++) {
        int a;
        scanf("%d", &a);
        ml.printCard(a);
    }
}
//--------------------------------------------------------------------------------
//SASAOJ-P_(리스트) 카드 나열하기 2
#include<stdio.h>
#include<stdlib.h>
struct Card { char k; int v; Card *next;};
class Clist {
  private:
    Card *head=NULL; int size=0;
  public:
    void insertCard(int idx, Card data);
    void printList();
};

//
void Clist::insertCard(int idx, Card data) {
    if(idx<=0||idx>size+1) return;
    Card *p=NULL, *t=head;
    Card *n=(Card*)malloc(sizeof(Card));
    *n=data;

    for(int i=1;t!=NULL&&i<idx;i++,p=t,t=t->next);
    n->next=t;

    if(p) // head -> ... -> p -> n -> t
        p->next=n;
    else
        head=n;
    size++;
}
void Clist::printList() {
    Card *t=head;
    for(;t!=NULL;t=t->next) {
        printf("%c%d ", t->k, t->v);
    }
}
//

int main() {
  Card c;
  Clist list;
  int idx;
  for(int i=0;i<10;i++) {
    scanf(" %c %d %d",&c.k, &c.v, &idx);
    list.insertCard(idx, c);
  }
  list.printList();
}
//--------------------------------------------------------------------------------
//SASAOJ-Q_(리스트) 카트 나열하기 3
#include<stdio.h>
#include<stdlib.h>
struct Card { char k; int v; Card *next;};
class Clist {
  private:
    Card *head=NULL; int size=0;
  public:
    void insertCard(int idx, Card data);
    void reverse();
    void printList();
};

//
void Clist::insertCard(int idx, Card data) {
    if(idx<=0||idx>size+1) return;
    Card *p=NULL, *t=head;
    Card *n=(Card *)malloc(sizeof(Card));
    *n=data;

    for(int i=1;i<idx;i++,p=t,t=t->next);
    n->next=t;

    if(p)
        p->next=n;
    else
        head=n;
    size++;
}
void Clist::reverse() {
    Card *p=NULL, *t=head;
    while(head) {
        head=head->next;
        t->next=p;
        p=t;
        t=head;
    }
    head=p;
}
void Clist::printList() {
    Card *t=head;
    for(;t!=NULL;t=t->next) {
        printf("%c%d ", t->k, t->v);
    }
}
//

int main() {
  Card c;
  Clist list;
  int idx,n,k;
  scanf("%d%d",&n,&k);
  for(int i=1;i<=n;i++) {
    scanf(" %c %d %d",&c.k, &c.v, &idx);
    if(i%k) list.insertCard(idx, c);
    else list.reverse();
  }
  list.printList();
}
//--------------------------------------------------------------------------------
//SASAOJ-R_(리스트) 희소 다항식의 덧셈
#include <stdio.h>
#include <stdlib.h>
struct Term { int coe, exp; Term *next; };
struct Poly {
  private:
    Term *head=NULL;
  public:
    void insertTerm(Term X);
    void printPoly();
};

void Poly::insertTerm(Term X) {
    Term *p=NULL, *t=head;
    for(;t!=NULL&&t->exp>X.exp;p=t,t=t->next);
    if(t&&t->exp==X.exp) {
        t->coe+=X.coe;
        return;
    }

    Term *n=(Term *)malloc(sizeof(Term));
    *n=X;
    n->next=t;

    if(p)
        p->next=n;
    else
        head=n;
}
void Poly::printPoly() {
    Term *t=head;
    while(t) {
        if(t->coe) { // 계수가 0이 아님
            printf("%d", t->coe);
            if(t->exp) { // 차수 1 이상
                printf("x");
                if(t->exp>1) printf("^%d", t->exp);
            }
        }
        t=t->next;
        if(t!=NULL) {
            if(t->coe>0)
                printf("+");
        }
    }
}

int main() {
    int n;
    Term X;
    Poly poly;
    scanf("%d", &n);

    for(int i=0; i<n; i++) {
        int k;
        scanf("%d", &k);

        for(int j=0; j<k; j++) {
            scanf("%d %d", &X.coe, &X.exp);
            poly.insertTerm(X);
        }
    }
    poly.printPoly();
}
//--------------------------------------------------------------------------------
//SASAOJ-S_(리스트)전치행렬 만들기
#include <stdio.h>
#include <stdlib.h>
struct Node { int x, y, val; Node *next; };
struct matrix {
  private:
    Node *head;
    int row=0, col=0;
  public:
    void setRowCol(int Row, int Col) { row=Row, col=Col; };
    void insertNode(Node X);
    void printMat();
};

void matrix::insertNode(Node X) {
    Node *p=NULL, *t=head;
    Node *n=(Node*)malloc(sizeof(Node));
    *n=X;

    for(;t && t->x<=X.x && t->y<=X.y;p=t, t=t->next);
    n->next=t;

    if(p)
        p->next=n;
    else
        head=n;
}
void matrix::printMat() {
    Node *t=head;
    for(int i=0; i<row; i++) {
        for(int j=0; j<col; j++) {
            if(t&&t->x==i&&t->y==j) {
                printf("%d ", t->val);
                t=t->next;
            }
            else printf("0 ");
        }
        puts("");
    }
}

int main() {
    int n, m;
    matrix mt;
    scanf("%d %d", &n, &m);
    mt.setRowCol(m, n);

    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            int a;
            scanf("%d", &a);

            if(a)
                mt.insertNode({j, i, a});
        }
    }
    mt.printMat();
}
//--------------------------------------------------------------------------------
//SASAOJ-T_(Stack) 컵 쌓기 1
#include<stdio.h>
#include<stdlib.h>

struct ArrayStack {
  private:
    int size,top,cnt; //배열크기,top의 위치,아이템개수
    int * s;
  public:
    void createAS(int n); // 항목수가 최대 n개인 ArrayStack 생성하기
    void push(int d); // int d를 넣기
    int pop();  // 최상위 int 꺼내기
    bool isEmpty(); // 빈 스택 판별
};

//
void ArrayStack::createAS(int n) {
    s=(int *)malloc(sizeof(int)*(n+10));

    if(s) {
        top=cnt=0;
        size=n;
    }
}
void ArrayStack::push(int d) {
    if(cnt==size) return;

    s[top++]=d;
    cnt++;
}
int ArrayStack::pop() {
    if(top==0) return 0;

    cnt--;
    return s[--top];
}
bool ArrayStack::isEmpty() {
    return !cnt;
}
//

int main() {
  int n,k,a,b,c;
  ArrayStack s[3];
  scanf("%d%d",&n,&k);
  for(int i=0;i<3;i++) s[i].createAS(n);
  for(int i=1;i<=n;i++)
    s[0].push(i);
  for(int i=0;i<k;i++) {
    scanf("%d%d",&a,&b);
    c=s[a].pop();
    if(c) s[b].push(c);
  }
  for(int i=2;i>=0;i--)
    while(!s[i].isEmpty())
      printf("%d ",s[i].pop());
  return 0;
}
//--------------------------------------------------------------------------------
//SASAOJ-U_(Stack) 컵 쌓기 2
#include<stdio.h>
#include<stdlib.h>
struct Node { int no; Node *next; };
struct LinkedListStack {
  private:
    int cnt=0;
    Node *top=NULL;
  public:
    void push(int d);
    int pop();
    bool isEmpty();
};

//
void LinkedListStack::push(int d) {
    Node *n=(Node *)malloc(sizeof(Node));
    n->no=d;

    n->next=top;
    top=n;
    cnt++;
}
int LinkedListStack::pop() {
    if(cnt==0) return 0;

    Node *t=top;
    int data=top->no;

    top=top->next;
    free(t);
    cnt--;

    return data;
}
bool LinkedListStack::isEmpty() {
    return !cnt;
}
//

int main() {
  int n,k,a,b,c;
  LinkedListStack s[3];
  scanf("%d%d",&n,&k);
  for(int i=1;i<=n;i++)
    s[0].push(i);
  for(int i=0;i<k;i++) {
    scanf("%d%d",&a,&b);
    c=s[a].pop();
    if(c) s[b].push(c);
  }
  for(int i=2;i>=0;i--)
    while(!s[i].isEmpty())
      printf("%d ",s[i].pop());
  return 0;
}
//--------------------------------------------------------------------------------