// 只插入到当前头节点的后边
void CreateListHead(LinkList *L, int n){
  LinkList p;
  int i;
  srand(time(0));
  // 给新的头节点分配存储空间
  *L = (LinkList)malloc(sizeof(Node));
  (*L)->next = null;
  for(i=0;i<n;i++){
    p = (LinkList)malloc(sizeof(Node));
    p->data = rand()%1024+1;
    p->next = (*L)->next;
    (*L)->next = p;
  }
}

// 尾插法 插入到单链表的末端
void CreateListTail(LinkList *L, int n){
  LinkList p,r;
  int i;
  srand(time(0));
  // 创建整个线性表的存储空间
  *L = (LinkList)malloc(sizeof(Node));
  r = *L;
  for(i=0;i<n;i++){
    p = (Node*)malloc(sizeof(Node)); //注意这个部分
    p->data = rand()%1024+1;
    r->next = p;
    r = p;
  }
  r->next = null;
}

bool ClearList(LinkList *L){
  LinkList p,q;
  p = (*L)->next;
  while(p){
    q = p->next;
    free(p);
    p = q;
  }
  (*L)->next = null;
  return true;
}

typedef struct{
  int data;
  int cur; //相当于动态链表中的next
}Component,StaticLinkList[MAXSIZ];

// 初始化一个静态链表
bool InitList(StaticLinkList space){
  int i ;
  for(i=0;i<MAXSIZE-1;i++){
    space[i].cur = i+1;
  }
  space[MAXSIZE-1] = 0;
  return true;
}
//

// 定义栈的数据结构
typedef struct
{
  int data[MAXSIZE]; //记录一个数组来存放栈中的元素
  int top; // 设定一个栈顶指针
}

typedef struct{
  int data[MAXSIZE];
  int top1;
  int top2;
}SqDoubleStack;

bool Push( SqDoubleStack *S, int *e, int stackNumber){
  if(S->top1+1 == S->top2){
    return false;
  }
  if (StackNumber == 1)	S->data[++S->top1] = e;
  if (StackNumber == 2)	S->data[--S->top2] = e;
  return true;
}

bool Pop(SqDoubleStack *S, int *e, int stackNumber){
  if (StackNumber == 1){
    if(S->top1 == -1) return false;
    *e = S->data[S->top1--];
  }else if (StackNumer == 2){
    if(S->top2 == MAXSIZE) return false;
    *e = S->data[S->top2++];
  }
  return true;
}

// 定义一个链式的存储结构
typedef struct StackNode{
  int data;
  struct StackNode *next;
}StackNode, *LinkStackPtr;

// 用来指示栈的当前栈顶的位置
typedef struct LinkStack{
  LinkStackPtr top; // 这个结构指向栈顶的地址空间
  int count; // 栈的大小
}

// 入栈操作
bool Push( LinkStack *S, int e){
  LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
  s->data = e;
  s->next = S->top;
  S->top = s; // 将栈顶的空间复制给新创建的s
  S->count++;
  return true;
}

// 出栈操作
bool Pop( LinkStack *S, int *e){
  // 定义一个指针
  LinkStackPtr p;
  if(*S == null) return false;
  *e = S->top->e;
  p = S->top;
  S->top = S->top->next;
  free(p);
  S->count--;
  return true;
}

// 时间复杂度都是 O(1) 因为是线性的问题。

// 我们来定义队列的数据结构

typedef struct{
  int data[MAXSIZE];
  int front;
  int rear;
}SqQueue;

bool InitQueue(SqQueue *Q){
  Q->front = 0;
  Q->rear = 0;
  return true;
}

bool EnQueue (SqQueue *Q, int e){
  if((Q->rear+1)%MAXSIZE == Q->front) return false;
  Q->data[Q->rear] = e;
 	Q->rear = (Q->rear+1) % MAXSIZE;
  return true;
}

bool DeQueue (SqQueue *Q, QElemType *e){
  if (Q->front == Q->rear) return false;
  *e = Q->data[Q->front];
  Q->front = (Q->front+1) %MAXSIZE;
  return true;
}

typedef struct QNode{
  int data;
  struct QNode *next;
}QNode,*QueuePtr;

typedef struct
{
  QueuePtr front,rear;
}LinkQueue;

// 插入队列
bool EnQueue(LinkQueue *Q, int e){
  QueuePtr s = (QueuePtr) malloc(sizeof(QNode));
  if(!s) exit(OVERFLOW);
  s->data = e;
  s->next = null;
  Q->rear->next = s;
  Q->rear = s;
  return true;
}

// 出队列
bool DeQueue(LinkQueue *Q, int *e){
  QueuePtr = s;
  if(Q->front == Q->rear) return false;
  p = Q->front->next;
  *e = p->data;
  Q->front->next = p->next;
  if(Q->rear == p) Q->rear = Q->front;
  free(p);
  return true;
}

int Index(String S, String T, int pos){
  
  int i = pos;
  int j = 1;
  
  while(i<=S[0] && j<=T[0])
  {
    if( S[i] == T[j]){
      ++i;
      ++j;
    }
    else
    {
      i = i-j+2;
      j = 1;
    }
    if( j>T[0])
      return i-T[0];
    else
      return 0;
  }
}

// 时间复杂度 最好的情况下就是 O(1)  比较差的情况是 O(n+m)
// 比较差的情况是 O((n-m+1)*m)

// 二叉树的表结点的结构定义

typedef struct BiTNode
{
  int data;
  struct BiTNodde *lchild, *rchild;
} BiTNode, *BiTree;

void PreOrderTraverse(BiTree T)
{
  if(T == NULL)
    return;
  print("%d", T->data);
  PreOrderTraverse(T->lchild);
  PreOrderTraverse(T->rchild);
}

void PreOrderTraverse(BiTree T)
{
  if(T == NULL)
    return;
  PreOrderTraverse(T->lchild);
  print("%d", T->data);
  PreOrderTraverse(T->rchild);
}

//中序遍历非递归版
void InOrderWithoutRecursion1(BTNode* root)
{
    //空树
    if (root == NULL)
        return;
    //树非空
    BTNode* p = root;
    stack<btnode*> s;
    while (!s.empty() || p)
    {
        //一直遍历到左子树最下边，边遍历边保存根节点到栈中
        while (p)
        {
            s.push(p);
            p = p->lchild;
        }
        //当p为空时，说明已经到达左子树最下边，这时需要出栈了
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            cout << setw(4) << p->data;
            //进入右子树，开始新的一轮左子树遍历(这是递归的自我实现)
            p = p->rchild;
        }
    }
}</btnode*>

void PreOrderTraverse(BiTree T)
{
  if(T == NULL)
    return;
  PreOrderTraverse(T->lchild);
  PreOrderTraverse(T->rchild);
  print("%d", T->data);
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
      if(!root) return True; // 如果是空的那一定是平衡的
      if(abs(depth(root->left),depth(root->right))>1) return False;
      return isBalanced(root->left) && isBalanced(root->right);
    }
  	int depth(TreeNode* tree){
      if(!tree) return 0;
      int leftheight = depth(tree->left);
      int rightheight = depth(tree->right);
      return leftheight>rightleft? leftheight+1:rightleft+1;
    }

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return !root ? true : abs(depth(root->left) - depth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
    int depth(TreeNode* cur) { //计算二叉树的最大深度
        return !cur ? 0 : max(depth(cur->left), depth(cur->right)) + 1;
    }
};

// 递归
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

        if(l1 == nullptr){
            return l2;
        }
        if (l2 == nullptr){
            return l1;
        }
        if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
    }
};

#include <stack>
class CQueue {
public:
    stack<int> stack1;
    stack<int> stack2;
    CQueue() {

    }
    
    void appendTail(int value) {
        stack1.push(value);
    }
    
  	// 需要出队列的是 stack2 的栈顶元素或者是stack1的栈底元素 没出去一个元素就要pop掉
    int deleteHead() {
        int ans;
        if(stack1.empty() && stack2.empty()) return -1;
        if(!stack2.empty()){
            ans = stack2.top();
            stack2.pop();
            return ans;
        }else if(!stack1.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
            ans = stack2.top();
            stack2.pop();
            return ans;
        }
        return ans;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int>s;
        int length = pushed.size();
        int j = 0;
        for(int i=0;i<length;i++){
            s.push(pushed[i]);
            while(j<length && j<=i && s.top() == popped[j] ){
                    s.pop();
                    j++;
            }
        }
        if(s.empty())
            return true;
        else
            return false;
    }
};

class MinStack {
public:
    /** initialize your data structure here. */
    stack <int> inStack;
    stack <int> outStack;
    MinStack() {
    }
    
    void push(int x) {
        inStack.push(x);
        if(outStack.empty() || outStack.top()>=x)outStack.push(x);
    }
    
    void pop() {
        if(inStack.top() == outStack.top()) outStack.pop();
        inStack.pop();
    }
    
    int top() {
        return inStack.top();
    }
    
    int min() {
        return outStack.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */

// 优先队列
#include <iostream>
#include <stdlib.h>
#include <stack>
#include <list>
#include <random>
#include <queue>
using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

class Solution {
public:
    struct cmp{
        bool operator()(ListNode*a, ListNode*b){
            return a->val>b->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp>(pri_queue);
        for(auto item: lists)
            pri_queue.push(item);
        //设定一个哨兵节点
        ListNode dummy(-1);
        ListNode* q = &dummy;
        while(!pri_queue.empty()){
            ListNode* top = pri_queue.top();
            pri_queue.pop();
            q->next= top;
            q = top;
            if(top->next) pri_queue.push(top->next);
        }
        return dummy.next;
    }
};

class Solution {
public:
    // 小根堆的回调函数
    ListNode* merge(ListNode* p1, ListNode* p2){
        if(!p1) return p2;
        if(!p2) return p1;

        if(p1->val <= p2->val){
            p1->next = merge(p1->next, p2);
            return p1;
        }else{
            p2->next = merge(p1, p2->next);
            return p2;
        }
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return nullptr;
        ListNode* head = lists[0];
        for(int i=0; i<lists.size(); i++){
            if(lists[i])
                head = merge(head,lists[i]);
        }
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //快慢指针
        ListNode* slow = head;
        ListNode* fast = head;
        //开始进行第一次来回指针
        while( fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                fast = head;
                while(slow != fast){
                    slow = slow->next;
                    fast = fast->next;
                }
                return fast;
            }
        }
        return nullptr;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //快慢指针
        ListNode* slow = head;
        ListNode* fast = head;
        vector<ListNode*> list;
        //开始进行第一次来回指针
        while( slow->next!=nullptr && fast != nullptr && fast->next != nullptr && fast->next->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
            //使用堆栈的方式
            if(slow == fast){
                while(find(list.begin(),list.end(),slow) == list.end())
                {
                    list.push_back(slow);
                    slow = slow->next;
                }
                ListNode* temp = head;
                while(find(list.begin(),list.end(),temp) == list.end()){
                    temp = temp->next;
                }
                return temp;
            }
        }
        return nullptr;
    }
};

#include <iostream>
#include <string.h>
using namespace std;
char str[5000];
int main(){
    cin.get(str,5000);
    int length =strlen(str);
    if(length==0) cout<<0<<endl;
    int ans = 0;
    while(str[length-1]!=' '&&length>0){
        length--;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

#include<iostream>
#include<string.h>
using namespace std;
int main(){
    char str[2000];
    char target_char;
    cin.get(str,2000);
    cin>>target_char;
    int length = strlen(str);
    int ans = 0;
    while(length>0){
        if(str[length-1] == target_char || str[length-1] == tolower(target_char) || str[length-1] == toupper(target_char)) ans++;
        length--;
    }
    cout<<ans<<endl;
    return 0;
}

#include<iostream>
#include<set>
using namespace std;

int main(){
    int N,n;
    set<int> ans;
    while(cin>>N){
        ans.clear();
        while(N--){
            cin>>n;
            ans.insert(n);
        }
        for(set<int>::iterator it=ans.begin();it!=ans.end();it++){
            cout<<*it<<endl;
        }
    }
    return 0;
}

#include<iostream>
using namespace std;

void Deal(string s){
    if(s.size()<=8){
        int judge= 8-s.size();
        for(int i=0; i<judge;i++){
            s += '0';
        }
        cout<<s<<endl;
    }else{
        string next(s,0,8);
        cout<<next<<endl;
        s.erase(s.begin(),s.begin()+8);
        Deal(s);
    }
}

int main(){
    string str1;
    string str2;
    cin>>str1;
    cin>>str2;
    Deal(str1);
    Deal(str2);
    return 0;
}

// C++
#include<iostream>
#include<string>
#include<cmath>
using namespace std;

int main(){
    string hex_value;
    while(cin>>hex_value){
        int bit=0;
        int ans=0;
        for(int i=hex_value.length()-1;i>1;i--){
            if(hex_value[i]>='0'&& hex_value[i]<='9')
                ans += (hex_value[i]-'0')*pow(16,bit++);
            else if(hex_value[i]>='A'&&hex_value[i]<='F')
                ans += (hex_value[i]-'A'+10)*pow(16,bit++);
        }
        cout<<ans<<endl;
    }
    return 0;
}

#include<iostream>
#include<string>
using namespace std;

int main(){
    long int num;
    cin>>num;
    for(int i=2;i<num+1;i++){
        while(num%i==0){
            cout<<i<<' ';
            num/=i;
        }
    }
    cout<<endl;
    return 0;
}
// Python 与此思想相似不予举例

#include<iostream>
using namespace std;

int main(){
    float num;
    cin>> num;
    int integar = num / 1.0;
    float decimal = num - integar;
    if(decimal<0.5){
        cout<<(integar)<<endl;
    }else{
        cout<<(integar+1)<<endl;
    }
    return 0;
}

#include <iostream>
#include <set>
#include <map>
using namespace std;

int main(){
    int num;
    map<int, int> m;
    cin>>num;
    for(int i=0;i<num;i++){
      	//输入成对使用pair关键字
        pair<int,int> arr;
        cin>>arr.first;
        cin>>arr.second;
        if((m.find(arr.first))!=m.end())
            m[arr.first] += arr.second;
        else
            m[arr.first] = arr.second;
    }
    for(auto it=m.begin();it!=m.end();it++)
        cout<<it->first<<" "<<it->second<<endl;
    return 0;
}

#include <iostream>
#include <string>
using namespace std;
int main()
{
   // cout << "hello" << endl;
    int n;
    while(cin >> n) {
        while(n--) {
            string str1;
            cin >> str1;
            while(str1.size() > 8) {
                cout << str1.substr(0, 8) << endl;
                str1 = str1.substr(8);
            }
            while(str1.size() != 8) {
                str1 += '0';
            }
            cout << str1 << endl;
        }
 
   }
}

#include <iostream>
#include <string>
using namespace std;

int main(){
    string str;
    getline(cin,str);
    int count = 0;
    int len = str.length();
    for(int i=len-1;i>=0;i--){
        if(str[i]!=' ') count++;
        else break;
    }
    cout<<count;
    return 0;
}

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

bool checkPoPRule(int* pop, int* push, int len){
    if(pop == NULL || push == NULL || len<=0) return false;
    stack<int>Stack;
    int i=0,j=0;
    for(i = 0; i<len; i++){
        Stack.push(push[i]);
        while(j<len && Stack.size() !=0 && pop[j]==Stack.top())
        {
            Stack.pop();
            j++;
        }
    }
    return Stack.empty();
}

int main(){
    int N;
    while (cin>>N){
        int *pop = new int [N];
        int *push = new int [N];
        for(int i=0; i<N; i++){
            cin>>push[i];
            pop[i] = push[i];
        }
        // 结束后为pop做一次排序来保证初始化的完全性
        sort(pop,pop+N);
        // 为输出预测的pop进行一次全排列
        do {
            if(checkPoPRule(pop,push,N)){
                for (int i = 0; i < N-1; ++i) {
                    cout<<pop[i]<<' ';
                }
                cout<<pop[N-1]<<endl;
            }

        }while (next_permutation(pop,pop+N));
    }
    return 0;
}

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
  	// 用栈反转链表
    ListNode* ReverseList(ListNode* pHead) {
      if(pHead == nullptr || pHead->next == nullptr)
        return pHead;
      ListNode* p = pHead;
      stack<ListNode*>s;
      // 先进栈
      while(p->next){
        s.push(p);
        p = p->next;
      }
      p->next = nullptr;
      // 再出栈
      ListNode* q = p; // q 为头指针
      while(!s.empty()){
        p->next = s.top();
        p = p->next;
        s.pop();
      }
      p->next = nullptr;
      return q;
	}
  
  // 递归方法
  ListNode* ReverseList_Recursion(ListNode* pHead){
    if(pHead == nullptr || pHead->next == nullptr) return pHead;
    // 先进行反转 
    ListNode* ReverserNodes = ReverseList_Recursion(pHead->next);
    // 再将当前节点设置为后面节点的后续节点
		pHead->next->next = pHead;
    pHead->next = nullptr;
    return RecerserNodes;
  }
}

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <list>
#include <cmath>
using namespace std;

bool CheckIpV4(string &str){
    stack<char>s1;
    double num = 0;
    int length;
    int count = 0;
    string c;
    if(str.empty()) return false;
    for(auto i: str){
        if(i != '.') {
            s1.push(i);
        }
        else{
            length  = s1.size();
            count++;
            if(count>3 || length>3) return false;
            for(int j=0; j<length; j++){
                c = s1.top();
                num += (stoi(c))*(pow(10,j));
                s1.pop();
            }
            if(num<0.0 || num>255.0) return false;
            num = 0;
        }
    }
    return true;
}

int main(){
    bool label = false;
    string s1 = "192.168.1.1";
    label = CheckIpV4(s1);
    cout<<label<<endl;
    return 0;
}

class CMyString{
public:
 	CMyString(char* pData = nullptr);
  CMyString(const CMyString& str);
  ~CMyString(void);
private:
  char *m_pData
}

CMyString& CMyString::operator = (const CMyString &str)
{
  if(this != &str){
    CMyString strTemp(str);
    char *pTemp = strTemp.m_pData;
    strTemp.m_pData = m_pData; //自动调用析构函数来释放内存
    m_pData = pTemp; // 赋值新的数据
  }
  return *this;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

double Power(int base, int exponent){

    bool negative_label = false;
    if(base == 0 && exponent == 0) return 0;
    if(exponent == 0) return 1;

    // 如果底数是0且指数小于零
    if(base == 0 && exponent < 0){
        negative_label = true;
        return 0;
    }

    // 如果是指数小于零
    unsigned int abs_exponent;
    if(exponent < 0){
        abs_exponent = static_cast<unsigned int>(-exponent);
    }else{
        abs_exponent = static_cast<unsigned int>(exponent);
    }
    double result = 1 ;
    for(int i=0; i<abs_exponent; i++)
        result *= base;
    if(exponent <  0)
        return 1.0/result;
    return result;
}

int main(){
    int base,exponent;
    cin>>base>>exponent;
    cout<<Power(base,exponent);
    return 0;
}